LeetCode 子集 子集 II 遞增子序列

文章目錄

• ​​78. 子集​​
• ​​90. 子集 II​​
• ​​491. 遞增子序列​​

78. 子集

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void fun(int startIndex, const vector<int>& nums){
        ans.push_back(path);
        for(int i = startIndex; i < nums.size(); i++){
            path.push_back(nums[i]);
            fun(i + 1, nums);
            path.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        fun(0, nums);
        return ans;
    }
};      

90. 子集 II

由于是求子集，不要求傳回子集中數字的順序，可以對原數組進行排序

排序以後，橫向去重即可，橫向去重時，值得注意的是，同一樹層重複時，​

​used[i-1]=false​

​​，同一樹枝重複時，​

​used[i-1]=true​

​，

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> used;

    void func(int startIndex, const vector<int>& nums){
        ans.push_back(path);
        for(int i = startIndex; i < nums.size(); i++){
            if(i > startIndex && nums[i] == nums[i-1] && !used[i-1]){
                // 同一樹層，不出現重複的元素，同一樹層不使用重複元素，都是i > startIndex
                continue;
            }
            used[i] = true;
            path.push_back(nums[i]);
            func(i + 1, nums);
            path.pop_back();
            used[i] = false;
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        used.resize(nums.size());
        sort(nums.begin(), nums.end());
        func(0, nums);
        return ans;
    }
};      

491. 遞增子序列

由于求子序列，不能對原數組排序，比如數組[4,6,7,6]，如果排序，我們就會找出子序列[4,6,6,7]，但題目要求我們在原數組中找出遞增子序列，如果是在原數組中找遞增子序列，就不應該出現[4,6,6,7]，是以不能排序

• 橫向限制：同一樹層不能出現相同的數字
• 縱向限制：同一樹枝往下深入時，不能出現孩子節點比父親大的情況

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    void func(int startIndex, const vector<int>& nums){
        if(path.size() > 1){
            ans.push_back(path);
        }
        // 改用哈希表去重，而不用數組
        // used不能是全局變量，used隻用來記錄目前樹層使用過的元素
        unordered_set<int> used;
        for(int i = startIndex; i < nums.size(); i++){
            if(i > startIndex && used.find(nums[i]) != used.end()){
                // 橫向限制，同一樹層，不能出現相同的數字
                continue;
            }
            if(!path.empty() && nums[i] < path.back()){
                // 縱向限制，不能比前面使用過的小
                continue;
            }
            used.insert(nums[i]);
            path.push_back(nums[i]);
            func(i + 1, nums);
            path.pop_back();
        }
    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        func(0, nums);
        return ans;
    }
};