LeetCode #491：Increasing Subsequences(递增子序列)

题目描述

求递增子序列有点像是取有序的子集，而且本题也要求不能有相同的递增子序列，很容易就产生思维定式使用 “组合总和II” 的方法（先排序再用类似 i > startIndex && nums[i] == nums[i – 1] 的条件去重）。然而根据本题题意，nums 数组是不能排序的（不然排完序的数组就都是递增子序列了），使用之前的去重逻辑就有问题了。故本题在去重时需要设置一个 set 进行检测（由于数组的数据范围在 [-100, 100]，也可换成长度为 201 的标记数组）。

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        n = nums.size();
        dfs(nums, 0);

        return res;
    }

    vector<vector<int>> res;
    vector<int> path;
    int n;

    void dfs(vector<int>& nums, int j) {

        if(path.size() >= 2) {           
            res.push_back(path);
            // 不能写return，要取整棵树的结点而不仅仅取叶子结点
        } 

        unordered_set<int> uset; // 使用set来对本层元素进行去重，注意不要放在类的成员变量里
        for(int i = j; i < n; i ++) {
            if((!path.empty() && path.back() > nums[i]) || uset.find(nums[i]) != uset.end()) // 当遍历到的数非递增、或在本层出现过后剪枝
                continue;
            
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
    }
};

需要注意，unordered_set<int> uset 仅记录本层元素是否重复使用，进入下一层 set 都会重新定义（清空）。在树形结构中，如果把 set 放在类成员的位置（相当于全局变量），就把树枝的情况都记录了，不是单纯的控制某一节点下的同一层了。

使用标记数组优化后的版本如下。

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        n = nums.size();
        dfs(nums, 0);

        return res;
    }

    vector<vector<int>> res;
    vector<int> path;
    int n;

    void dfs(vector<int>& nums, int j) {

        if(path.size() >= 2) {           
            res.push_back(path);
            // 不能写return，要取整棵树的结点
        } 

        int flag[201] = {0}; // 使用标记数组
        for(int i = j; i < n; i ++) {
            if((!path.empty() && path.back() > nums[i]) || flag[nums[i] + 100] == 1) // 当遍历到的数非递增、或在本层出现过后剪枝
                continue;
            
            flag[nums[i] + 100] = 1;
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
    }
};