回溯问题中组合、子集和排列问题的去重

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

• 组合问题：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数组，不用移除元素 } }