回溯法，⼀般可以解决如下⼏种问题：

• 组合问题：N个数⾥⾯按⼀定规则找出k个数的集合
• 切割问题：⼀个字符串按⼀定规则有⼏种切割⽅式
• ⼦集问题：⼀个N个数的集合⾥有多少符合条件的⼦集
• 排列问题：N个数按⼀定规则全排列，有⼏种排列⽅式
• 棋盘问题：N皇后，解数独等等

本文主要讲解这几种问题在去重问题上的不同做法，其实就一个核心点，<font color=red>对有序数组进行去重，去重方式包括传递used引用去重和每层定义set去重</font>。

需知：组合问题、切割问题和子集问题无序，排列问题有序

• 对于组合问题，因为组合无序，所以需要排序+used/set去重，组合问题其实是子集问题的一种；

• 对于切割问题，本质就是组合问题，使用startIdx当作切割下标即可；

• 对于子集问题，包括两种题型：

  • 子集II：和组合问题去重一样，排序+used/set去重
  • 递增子序列：等价于从有序数组中选取所有子集，相当于有序数组的前提已经实现，所以需要使用set进行去重,不能使用used是因为不能进行candidates[i] == candidates[i-1] && used[i-1]==false的判断

• 对于排列问题，说下解题思路和去重问题：

  • 解题思路：

    1. 每层递归都是从0开始搜索；
    2. 使用used数组记录path里面放了哪些元素

  • 去重问题：

    1. 不用排序，每层定义set去重(只有这一种情况特殊不用排序)

       int repeatArr[21] = {0};
       for (int i = 0; i < nums.size(); i++) {
           if (repeatArr[nums[i] + 10] == 1 || used[i]) {  // 在当前节点之前出现过该数值的节点
               continue;
           }
           repeatArr[nums[i] + 10] = 1;
       }
    

    2. 和组合问题一样，先排序，在传递used引用去重

    void backtracking(vector<int> &nums, vector<bool> &used)
    {
        for (int i = 0; i < nums.size(); i++) {
            // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
            if ((i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) || used[i]){
                continue;
            }
        }
    }
    

    3. 扩展(树枝去重)

    对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更⾼！
    树枝去重即：
    if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true || used[i]) {
        continue;
    }
    

• 求和问题中，有序数组的剪枝问题：：for (int i = idx; i <= 9 - (k - path.size()) + 1 && sum+i<=n; i++){} //因为集合有序，当sum+i>n时，i之后的数sum+idx必然也大于n，因此加sum+i<=n在for循环判断条件处

思路：去重，即使用过的元素不能重复选取。**<font color=red>组合和子集问题中，有序数组才能做树层去重。</font>**去重有两种思路：

1、**传递used引用只影响startIdx下标为头结点的整棵树；**当遍历到下标i时，如果candidates[i] == candidates[i-1] && used[i-1]==false,说明i-1是i节点在该树层的前节点，如果candidates[i] == candidates[i-1] && used[i-1] == true,说明i-1是i节点的父节点

注意：引用传递和全局变量在回溯中的使用方法一模一样，区别：如果需要使用题目给的nums数组的大小信息进行初始化的话，就在入口函数对used数组进行初始化，并传递引用；如果used不需要进行初始化，直接使用全局变量即可

// ⾸先把给candidates排序，让其相同的元素都挨在⼀起。
sort(candidates.begin(), candidates.end());
void backtracking(vector<int> &candidates, int target, int sum, int startIndex, vector<bool> &used)
{
    for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
        // used[i - 1] == true，说明同⼀树⽀candidates[i - 1]使⽤过
        // used[i - 1] == false，说明同⼀树层candidates[i - 1]使⽤过
        // 要对同⼀树层使⽤过的元素进⾏跳过
        if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
            continue;
        }
        used[i] = true;
        backtracking(candidates, target, sum, i + 1, used);
        used[i] = false;
    }
}

2、**每层定义set只影响startIdx下标开始的当前树层的节点。**如果set[nums[i]]=true,说明该节点之前已经存在数值为nums[i]的节点

void backtracking(vector<int> &candidates, int target, int sum, int startIndex)
{
    unordered_set<int> uset;  // 使⽤set对本层元素进⾏去重
    for (int i = startIndex; i < candidates.size(); i++) {
        // 要对同⼀树层使⽤过的元素进⾏跳过
        if (uset.find(candidates[i]) != uset.end() || sum + candidates[i] > target) {
        continue;
    }
        uset.insert(candidates[i]);
        backtracking(candidates, target, sum, i + 1);
        // 每层都拥有自己的used数组，不用移除元素
    }
}