491-递增子序列

LeetCode 491. Increasing Subsequences

LeetCode-491

Given an integer array nums, return all the different possible increasing subsequences of the given array with at least two elements. You may return the answer in any order.

The given array may contain duplicates, and two equal integers should also be considered a special case of increasing sequence.

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]]

method: 回溯

元素不能重复使用，所以i+1
类似子集问题，收集所有含有两个元素以上的子节点
数组有重复，但是子集不能重复，所以要同一树层的去重
但是又不能排序，不能使用数组总和II的去重方法

解决办法：使用一个集合记录元素是否被使用过

两个判断条件：

• 如果nums[i]比子集最后一个元素小，就不能放进来了
• 同一分支下，相同元素已经被记录使用过了就不能再用了

vector<vector<int>> ret;
vector<int> path;
void dfs(vector<int>& nums, int index) {
    if (path.size() > 1) {
        ret.push_back(path);    // 不用return
    }
    unordered_set<int> st;
    for (int i = index; i < nums.size(); ++i) {
        if ((!path.empty() && nums[i] < path.back()) || st.count(nums[i])) 
                continue;
        path.push_back(nums[i]);
        st.insert(nums[i]); // 记录已使用过
        dfs(nums, i + 1);   // 不能重复使用
        path.pop_back();
    }
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
    dfs(nums, 0);
    return ret;
}

改进

题目限制数组元素大小为[-100,100]，所以可以用数组替换unordered_set，速度更快一点

vector<vector<int>> ret;
vector<int> path;
void dfs(vector<int>& nums, int index) {
    if (path.size() > 1) {
        ret.push_back(path);
    }
    int used[201] = {0};
    for (int i = index; i < nums.size(); ++i) {
        if ((!path.empty() && nums[i] < path.back()) 
                || used[nums[i] + 100]) continue;
        path.push_back(nums[i]);
        used[nums[i] + 100] = 1;
        dfs(nums, i + 1);
        path.pop_back();
    }
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
    dfs(nums, 0);
    return ret;
}