Leetcode|組合變種|491. 遞增子序列（first索引+跳過非相鄰重複元素）

1 回溯法（first索引+跳過未排序重複元素）

剛開始分析題目時，考慮到輸入有重複元素，我先

sort

了一下，發現不行，因為題目要求是找到所給數組目前順序下的遞增序列。但是不同順序的兩個解被視為同1個解，是以适合用組合慣用技巧

first

索引，但要想去除輸入重複解的情況，又不能

sort

，那最通用的方法就是把目前層的選擇通通扔到

個

哈希集合

中，隻要有重複就選擇性

continue

【問題考察本質】：通用型組合去重（可去非相鄰重複而非sort後的相鄰去重）

本題政策

first索引避免亂序重複
跳過重複元素( set.count(nums[i]) 代替 nums[i-1] == nums[i] )

class Solution {
private:
    int size;
    vector<vector<int>> solution;
    vector<int> path;
public:
    void backtrack(vector<int>& nums, int first) {
        if (path.size() >= 2) 
            solution.emplace_back(path);
        unordered_set<int> set;
        // 1.first索引避免亂序重複
        for (int i = first; i < size; i++) {
            // 2.跳過重複元素(set.count(nums[i])代替nums[i-1] == nums[i])
            if (set.count(nums[i])) continue;
            if (!path.empty() && path.back() > nums[i]) continue;
            set.insert(nums[i]);
            path.emplace_back(nums[i]);
            backtrack(nums, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        size = nums.size();
        backtrack(nums, 0);
        return solution;
    }
};

複制

由于額外使用哈希集合來存儲決策樹每層的選擇，是以時間和存儲都高一點，可以使用哈希表進行優化，有興趣的讀者可以進一步思考

緻謝

圖檔來源于「代碼随想錄」公衆号，歡迎大家關注這位大佬的公号