Backtracking - 491. Incremental subsequence

1 Title Description

Give you an array of integers nums , Find and return all different increasing subsequences in the array , In increasing subsequence There are at least two elements . You can press In any order Return to the answer .

The array may contain duplicate elements , If two integers are equal , It can also be regarded as a special case of increasing sequence .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/increasing-subsequences

2 Title Example

Example 1：
Input ：nums = [4,6,7,7]
Output ：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

Example 2：
Input ：nums = [4,4,3,2,1]
Output ：[[4,4]]

3 Topic tips

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

4 Ideas

Binary enumeration can be implemented recursively , List all subsequences , Then judge whether it is legal ., We can get such code ：

List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
public void dfs(int cur, int[] nums) {
    
    if (cur == nums.length) {
    
        //  Judge whether it is legal , If the legal judgment is repeated , Add those that meet the conditions to the answer 
        if (isValid() && notVisited()) {
    
            ans.add(new ArrayList<Integer>(temp));
        }
        return;
    }
    //  If you select the current element 
    temp.add(nums[cur]);
    dfs(cur + 1, nums);
    temp.remove(temp.size() - 1);
    //  If you do not select the current element 
    dfs(cur + 1, nums);
}

This is a general template for recursively enumerating subsequences , That is, a temporary array temp To save the currently selected subsequence , Use cur To represent the subscript of the current position , stay dfs(cur,nums) Before the start ,[0, cur ―1] All elements in this interval have been considered , and [cur, n] The elements in this interval have not been considered . In execution dfs(cur,nums) when , We consider the cur Choose this position or not , If you select the current element , Then add the current element to temp in , Then recurse to the next position , At the end of recursion , Should be temp The last element of is deleted for backtracking ; If you don't select the current element , Recurses directly to the next location . Of course , If we simply enumerate like this , For each subsequence , We need to do it again O(n) The validity check and hash judgment of are repeated , During the execution of the whole program , We also need to use a space cost O(2") To maintain the hash value of the subsequence that has appeared . We can make some simple restrictions on choice and non choice , You can make the enumerated ones legal and not repeated :

• The way to legitimize the sequence is very simple , That is to 「 choice 」 Make a limit , This element can be selected only when the current element is greater than or equal to the last selected element , All the elements enumerated in this way are legal

• How to ensure that there is no repetition ? We need to give 「 No choice 」 Make a limit , Only when the current element is not equal to the last selected element , To consider not selecting the current element , Directly recurse the following elements . Because if there are two identical elements , We will consider four cases :

  1. The former is chosen , The latter was chosen
  2. The former is chosen , The latter is not chosen
  3. The former is not chosen , The latter was chosen
  4. The former is not chosen , The latter is not chosen

  The second case and the third case are actually equivalent , After we limit it like this , Abandon the second , The third one is reserved , So the goal of weight removal is achieved .

Complexity analysis

• Time complexity :o(2ⁿ*n). You still need to do binary enumeration of subsequences , Although the enumerated sequence omits the process of judging legitimacy and hashing , But it still needs O(n) Time to add to the answer .
• Spatial complexity :O(n). The space cost of temporary arrays here is O(n), The space cost of stack space used by recursion is also O(n).

5 My answer

class Solution {
    
    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> findSubsequences(int[] nums) {
    
        dfs(0, Integer.MIN_VALUE, nums);
        return ans;
    }

    public void dfs(int cur, int last, int[] nums) {
    
        if (cur == nums.length) {
    
            if (temp.size() >= 2) {
    
                ans.add(new ArrayList<Integer>(temp));
            }
            return;
        }
        if (nums[cur] >= last) {
    
            temp.add(nums[cur]);
            dfs(cur + 1, nums[cur], nums);
            temp.remove(temp.size() - 1);
        }
        if (nums[cur] != last) {
    
            dfs(cur + 1, last, nums);
        }
    }
}