491.非递减子序列

题目链接 文章讲解 视频讲解
层间去重：

• 回溯法相当于深搜，所以所以是一直递归到叶节点才开始回溯；
• 每次进入backtracking也就进入了搜索树的下一层，所以每进入一层需要用一个used_set来记录使用过的元素；

class Solution {
private:
    vector<int> sub;
    vector<vector<int>> result;
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums, 0);
        return result;
    }

    void backtracking(vector<int>& nums, int startIndex) {
        
        if(sub.size() >= 2) {
            result.push_back(sub);
        }

        unordered_set<int> used_set;
        for(int i = startIndex; i < nums.size(); ++i) {
            if((!sub.empty() && nums[i] < sub.back()) || used_set.find(nums[i]) != used_set.end()) continue;
            sub.push_back(nums[i]);
            used_set.insert(nums[i]);
            backtracking(nums, i + 1);
            sub.pop_back();
        }
    }
};

46.全排列

题目链接 文章讲解 视频讲解

同一个集合内不能使用已经用过的元素
不同集合之间可以使用已经用过的元素
排列问题需要选取所有的元素，所以不需要使用startIndex

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

public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }

    void backtracking(vector<int>& nums, vector<bool> used) {
        if(path.size() == nums.size()) {
            result.push_back(path);
            return ;
        }
        
        for(int i = 0; i < nums.size(); ++i) {
            if(used[i] == 1) continue;
            // 加入path后，标记为已使用
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            // 弹出元素时，标记为未使用
            used[i] = false;
        }
    }
};

47.全排列

题目链接 文章讲解 视频讲解

使用哈希表进行层间去重

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }

    void backtracking(vector<int>& nums, vector<bool>& used) {
        if(path.size() == nums.size()) {
            result.push_back(path);
            return ;
        }
        //  层间去重，去除相同的全排列
        unordered_set<int> used_set;
        for(int i = 0; i < nums.size(); ++i) {
            if(used[i] == true) continue;
            if(used_set.find(nums[i]) != used_set.end()) continue;
            used_set.insert(nums[i]);
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, used);
            used[i] = false;
            path.pop_back();
        }
    }

};

使用单个used数组进行去重

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtracking(nums, used);
        return result;
    }

    void backtracking(vector<int>& nums, vector<bool>& used) {
        if(path.size() == nums.size()) {
            result.push_back(path);
            return ;
        }
 
        for(int i = 0; i < nums.size(); ++i) {
            // used[i - 1] == false 说明同一层的nums[i - 1]已经用过应该跳过
            // used[i - 1] == true 说明同一树枝上的nums[i - 1]已经用过
            // 这里由于是排列间不能重复，所以used[i - 1] == false进行树层间去重
            if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;
            
            // 同一树枝上的元素值可以重复所以不用判断nums[i - 1], 但是不能用已经用过的元素所以used[i] == false;
            if(used[i] == false) {
                path.push_back(nums[i]);
                used[i] = true;
                backtracking(nums, used);
                used[i] = false;
                path.pop_back();
            }
        }
    }

};

关于去重

此题去重逻辑部分

if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;

改成：

if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) continue;

也可以通过。
这两种写法其实是数层去重和树枝去重的差别：
以{1， 1， 1}举例
第一种写法：

第二种写法：

可以看到两种去重方法都得到了正确的结果，但是数层去重更加高效