[leetcode] 491. Increasing Subsequences

我不是女神ヾ 2022-09-30 06:48 121阅读 0赞

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:  
Input: \[4, 6, 7, 7\]  
Output: \[\[4, 6\], \[4, 7\], \[4, 6, 7\], \[4, 6, 7, 7\], \[6, 7\], \[6, 7, 7\], \[7,7\], \[4,7,7\]\]  
Note:  
The length of the given array will not exceed 15.  
The range of integer in the given array is \[-100,100\].  
The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

题目：给一个整数数组，要求找到所有非减子序列，并且每个子序列的长度至少为2。  
【注意】  
1. 给定数组的长度不超过15  
2.整数的范围为\[-100, 100\]  
3. 数组中可能存在重复的数字，也可以算作一个子序列。

这道题可以采用深度优先搜索的方法解决。假设使用tmp来存储当前考虑的子序列，k表示tmp中最后一个元素的下标的后一个，则如果nums\[k\]的元素不小于tmp中的最后一个元素，就可以将其增加到tmp中，然后继续处理k+1处的元素，直到最后一个元素或者元素比最后一个小。接着返回原始的tmp，将nums\[k\]弹出，继续下一次dfs。

class Solution {
    public:
        vector<vector<int>> findSubsequences(vector<int>& nums) {
            set<vector<int>> res; // use set to filter same solution
            vector<int> tmp; // a solution item
            dfs(nums, res, tmp, 0);
            return vector<vector<int>> (res.begin(), res.end());
        }
    
    
        void dfs(vector<int>& nums, set<vector<int>>& res, vector<int> tmp, int k) {
    
            /*
                k: start index for DFS
             */
    
            if (tmp.size() >= 2) res.insert(tmp);
    
            for (int i = k; i < nums.size(); ++i) {
                // append element into tmp when it is empty 
                // or the new element is not less then the last element
                if (tmp.size() == 0 || nums[i] >= tmp.back()) {
                    tmp.push_back(nums[i]);
                    dfs(nums, res, tmp, i+1); //iteratively dfs among the remaining elements
                    tmp.pop_back(); 
                }
            }
        }
    };