C++刷题之旅（56）

LeetCode算法入门（第五十六天） 递归/回溯 78.子集

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

    void backtracking(vector<int>& nums, int starIndex){
        result.push_back(ans);
        //因为子集是无序的，{1,2}与{2，1}是一样的，所以取过的元素不能重复取，故for循环从startIndex开始，而不是0
        for(int i = starIndex; i < nums.size(); i++){
            ans.push_back(nums[i]);  //处理节点，收集元素
            backtracking(nums, i + 1);  //递归， 从i+1开始，元素不重复取
            ans.pop_back();   //回溯
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear();
        ans.clear();
        backtracking(nums, 0);
        return result;
    }
};

90.子集Ⅱ

本题与上一题的区别是，给定的数组中可能有重复元素，但是解集里不能有重复的解集，例如{1，2，2} 第一步取nums[0] = 1，第二步取nums[1] = 2后，第三步可以取nums[2] = 2，但是当回溯到重新取第二步的值时，由于前面已经取过nums[1] = 2，故本次不能再取nums[2] = 2。

用unordered_set存储已经去到的元素，在回溯后需要取元素时判断是否已经取过相同的值。

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

    void bracktracking(vector<int>& nums, int startIndex){
        result.push_back(path);
        unordered_set<int> uset;
        for(int i = startIndex; i < nums.size(); i++){
            //对同一层使用过的元素进行跳过
            if(uset.find(nums[i]) != uset.end()){
                continue;  //跳出本次循环
            }
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            bracktracking(nums, i+1);
            path.pop_back();    //回溯
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        path.clear();
        result.clear();
        sort(nums.begin(), nums.end());  //去重需要排序
        bracktracking(nums, 0);
        return result;
    }
};