摘要

• 在回溯法的树形结构的同一层中去重，可以使用set进行去重，这样无需重新排列待选元素。

• 全排列问题使用used数组来进行树枝去重（即在同一条路径上不使用相同的元素）更方便。

LeetCode491 递增子序列

491. 递增子序列 - 力扣（Leetcode）

• 这题的nums代表的是序列，要求的也是递增子序列。nums中的元素的顺序是不能改变的，不能对nums进行排序后来对连续分布的值相同的元素进行去重。只能通过在每层中引入一个set来记录当前层已经从哪些元素开始过。

• 以nums = [1, 2, 3, 1, 1]为例，其递增子序列的树形结构如下图

• 树层去重，其在回溯法的树形结构的同一层中，第一次选择值为x的元素时再往下的搜索结果，已经包含了在本层中再次选择值为x的元素的结果。也就是说，在同一层中，对于每个值x，只需要保留第一次遇到值为x的元素的搜索结果，再次遇到值为x的元素不需要再向下搜索。就可以完成树层去重。

完整的题解代码如下

class Solution {
public:
    void backtracking(vector<int>& nums, vector<vector<int>>& res, 
                    vector<int>& cur, int start) 
    {
        if (cur.size() >= 2) res.push_back(cur);
        if (start >= nums.size()) {
            return;
        }
        unordered_set<int> fused;
        for (int i = start; i < nums.size(); i++) {
            if (i - start && nums[i - 1] == nums[i]) continue;
            if (i - start && fused.count(nums[i])) continue;
            if (cur.empty() || nums[i] >= cur.back()) {
                cur.push_back(nums[i]);
                fused.insert(nums[i]);
                backtracking(nums, res, cur, i + 1);
                cur.pop_back();
            }
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> cur;
        map<int, bool> fused;
        backtracking(nums, res, cur, 0);
        return res;
    }
};

• 包含树层去重的回溯法的递归函数的结构

void backtracking(vector<int>& nums, vector<vector<int>>& res, 
                    vector<int>& cur, int start)
{
    if (/* 递归终止条件 */) {
        return;
    }
    
    /* 本层的局部变量 */
    
    for (int i = start; i < nums.size(); i++) {
        /* 向下搜索的逻辑 */
    }
}

LeetCode46 全排列

46. 全排列 - 力扣（Leetcode）

• 本题算是排列问题的入门，所以先复习一下组合和排列的概念，以便对比

而组合问题和排列问题都要进行“树枝去重”，即在树形结构的同一条路径上，不能重复使用同一个元素。组合问题和排列问题在“树枝去重”的实现上是不同的。

• 以[1,2,3]为例

• 在“全排列”的问题中，下一层元素也是要从第一个元素开始的，而不是从当前节点的下一个元素开始。所以，就需要一个数组来保存哪个元素使用过，哪个元素没有使用过。即used数组。

完整的题解代码如下

class Solution {
public:
    void backtracking(vector<int>& nums, vector<vector<int>>& res,
                    vector<int>& cur, vector<bool>& used) 
    {
        if (cur.size() == nums.size()) {
            res.push_back(cur);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            cur.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, res, cur, used);
            used[i] = false;
            cur.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> cur;
        vector<bool> used(nums.size());
        backtracking(nums, res, cur, used);
        return res;
    }
};

附组合问题的题解代码，以便对比

77. 组合 - 力扣（Leetcode）

class Solution {
public:
    void backtracking(vector<vector<int>>& res, int& n, int& k,
                     vector<int>& cur, int start)
    {
        if (cur.size() == k) {
            res.push_back(cur);
            return;
        }
        for (int i = start; i <= n - (k - cur.size()) + 1; i++) {
            cur.push_back(i);
            backtracking(res, n, k, cur, i + 1);
            cur.pop_back();
        }
        return;
    } 
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> cur;
        backtracking(res, n, k, cur, 1);
        return res;
    }
};

LeetCode47 全排列II

47. 全排列 II - 力扣（Leetcode）

• 以[1,1,2]为例，其树形结构如下

• 本题需要做“树层去重”：在同一层中，排除第一次选到值为x的元素之后再次选到值为x的元素的情况。
• 本题也需要做"树枝去重"：在同一条路径上，不能选取相同的元素。

用used数组来标记哪些元素使用过可以简单地实现树枝去重。

对于树层去重，一般有以下两种方式

• 一是用set进行树层去重，这适用于不可以改变待选元素序列的情况，对于可以对待选元素重新排序的情况，将待选元素重新排列后进行去重效率更高。
• 二是将待选元素进行重新排序，让值相同的元素连续分布，便于判断是否是第一次取到某个值的元素，这种实现方式比使用set效率高，但会改变待选元素本来的顺序。

使用unordered_set的题解代码

class Solution {
public:
    void backtracking(vector<int>& nums, vector<vector<int>>& res,
                    vector<int>& cur, vector<bool>& used) 
    {
        if (cur.size() == nums.size()) {
            res.push_back(cur);
            return;
        }
        unordered_set<int> level;
        for (int i = 0; i < nums.size(); i++) {
            if (used[i] || level.count(nums[i])) continue;
            cur.push_back(nums[i]);
            used[i] = true;
            level.insert(nums[i]);
            backtracking(nums, res, cur, used);
            used[i] = false;
            cur.pop_back();
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> cur;
        vector<bool> used(nums.size());
        backtracking(nums, res, cur, used);
        return res;
    }
};

重新排序待选元素的题解代码如下

class Solution {
public:
    void backtracking(vector<int>& nums, vector<vector<int>>& res,
                    vector<int>& cur, vector<bool>& used) 
    {
        if (cur.size() == nums.size()) {
            res.push_back(cur);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (i && nums[i - 1] == nums[i] && !used[i - 1]) continue;
            if (used[i]) continue;
            cur.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, res, cur, used);
            used[i] = false;
            cur.pop_back();
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> cur;
        vector<bool> used(nums.size());
        sort(nums.begin(), nums.end());
        backtracking(nums, res, cur, used);
        return res;
    }
};

image.png