“This is my 27th day of participating in the First Challenge 2022. For more details: First Challenge 2022.”

The title

Given an array of integers, nums, find and return all the different incrementing subsequences that have at least two elements in the array. You can return the answers in any order.

Arrays may contain duplicate elements, and the occurrence of two integers equal can also be considered a special case of increasing sequences.

Example 1

Output: input: nums =,6,7,7 [4], [[4, 6], [4, 6], [4,6,7,7], [4, 7], [4,7,7], [6, 7], [6,7,7], [7, 7]]Copy the code

Example 2

Nums = [4,4,3,2,1] output: [[4,4]]Copy the code

prompt

  • 1 <= nums.length <= 15
  • -100 <= nums[i] <= 100

Answer key

Train of thought

How is an increasing subsequence path generated? Its elements are selected one by one from NUMs. For example, [4,2,7,7], path takes the first number, and there are four options: nums[0] through nums[3]. Select nums[I], nums[I +1], nums[I +1], nums[I +1]… And so on, until there’s no choice left. When path meets the requirements, the solution set can be added, which is the idea of recursive backtracking.

Define recursive functions: push path to the appropriate number in the subarray from subscript start to the end. Path is also used as an argument. As you recurse, you keep picking numbers into your path.

In a recursive function, the for loop enumerates all current choices — expanding the different branches of the recursion

Select a number, push path, continue to select (continue to recurse)

When the start pointer reaches the boundary, all options are selected, there are no more numbers to choose from, and the recursion ends

Based on the current selection of recursion, all possibilities have been explored, at which point the path will undo the last digit and cut to another branch

code

const findSubsequences = (nums) = > {
  const res = [];
  const len = nums.length;

  const dfs = (start, path) = > {
    if (start == len) {    		// Recursive exit, pointer is out of bounds
      if (path.length >= 2) {   // The length of the path must be greater than or equal to 2
        res.push(path.slice()); // Add the solution set
        return;
      }
    }
    path.push(nums[start]);         // Select
    for (let i = start + 1; i <= len; i++) { // Enumerates options from start+1 to len
      const prev = nums[start];     // Select the upper level of the recursion tree
      const cur = nums[i];          // The current selection
      if (i < len && cur == prev) { // I is not out of bounds, and the current selection is the same as that of the previous layer
        dfs(i, path);               // Break the current selection to avoid I increment, resulting in I ==len
        // Avoid executing logic in else if, cause start==len, cause recursive exit, path pushed into res
        break;
      // I ==len oversteps the bounds, making it fall into recursion, returning at the exit of recursion
      } else if (i == len || prev < cur) { 
        // prev < curdfs(i, path); }}// Undo the selection
    path.pop();                     
  };
  for (let i = 0; i < len; i++) {
    dfs(i, []);
  }
  return res;
};
Copy the code

conclusion

Practice makes perfect, shortage in one; Success depends on forethought, destroyed by.