LeetCode 491 递增子序列

491.递增子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

回溯递归

本题和子集问题90.子集II存在类似，在给定的数组 nums 中存在重复元素，那么在寻找递增序列的过程中就存在着重复的递增子序列问题。

例如对于 nums=[4,7，4，6] 那么直接去寻找就会得到两个相同的递增子序列 [4,6] ，需要在结果中去掉这种重复。

但是本题相较于子集问题的不同之处在于：寻找的是当前序列的子序列，也就是元素的相对位置要和原序列中保持一致。例如 [4,4,3,1] 那么相应的递增子序列就只有 [4,4] ，因此是不能对元素进行排序的。

逐层选取的思想：本题的情形，可以使用一棵树来进行描述。树的第一层选取子序列中的第一个元素，树的第二层选取子序列的第二个元素，那么以序列 [4,7,6,7] 为例，选取元素构造树的过程为：

使用一个hash去记录那些元素被选取了，那么在当前层去选取元素时，需要两个判断：

1. nums[cur]>=tmp.back() 当前元素大于等于序列中的前一个元素
2. nums[cur] 这个元素在当前层没有被选取过（假设当前为i层，也就是要求 nums[cur] 没有做过序列中的第i个元素）

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;
    void DFS(vector<int>& nums,int cur){
        if(tmp.size()>1){
            res.push_back(tmp);
        }
        unordered_set<int> used;
        for(int i=cur;i<nums.size();i++){
            if((used.find(nums[i])!=used.end())||(!tmp.empty()&&nums[i]<tmp.back())){
                continue;
            }
            tmp.push_back(nums[i]);
            used.insert(nums[i]);
            DFS(nums,i+1);
            tmp.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        DFS(nums,0);
        return res;
    }
};

使用数组替代set实现：利用 nums 中的元素是 的，创建一个长度为201的数组全部置零即可实现对hash的替代：

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;
    void DFS(vector<int>& nums,int cur){
        if(tmp.size()>1){
            res.push_back(tmp);
        }
        int used[201]={0};
        for(int i=cur;i<nums.size();i++){
            if((used[nums[i]+100]==1)||(!tmp.empty()&&nums[i]<tmp.back())){
                continue;
            }
            tmp.push_back(nums[i]);
            used[nums[i]+100]=1; // 需要+100实现转化后的访问
            DFS(nums,i+1);
            tmp.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        DFS(nums,0);
        return res;
    }
};

参考链接

代码随想录