回溯算法章节小总结

1.树层去重

1.可以对原数组排序的

通过排序+相邻元素相同+used数组来进行去重

void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
      if (sum == target) {
          result.push_back(path);
          return;
      }
      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;
          }
          sum += candidates[i];
          path.push_back(candidates[i]);
          used[i] = true;
          backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
          used[i] = false;
          sum -= candidates[i];
          path.pop_back();
      }
  }

2.原数组不可以排序的，可以用哈希表

90. 子集 II - 力扣（LeetCode）（本题可以排序）

使用set哈希表来对同一层选过的元素进行标记

void backtracking(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]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }

2.树枝去重

1.一般是在参数index处去除，传入i+1就避免了这一问题

2.排序+used数组

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

vector<vector<int>> result;
   vector<int> path;
   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] == true，说明同一树枝nums[i - 1]使用过
           // used[i - 1] == false，说明同一树层nums[i - 1]使用过
           // 如果同一树层nums[i - 1]使用过则直接跳过
           if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
               continue;
           }
           if (used[i] == false) {
               used[i] = true;
               path.push_back(nums[i]);
               backtracking(nums, used);
               path.pop_back();
               used[i] = false;
           }
       }
   }

3.区间切割

问题模板：

重点是理解区间[index,i]的使用

res结果集;
bool is([index,i]区间)
{
    //判断合法性
    return true or false;
}
void backtracking(函数参数)
{
    if(终止条件)
    {
        res结果收集;
	}
    for(int i=index;i<s.size();i++)
    {
        if(is(传入[index,i]这个区间))
            path收集;
        else
            break or continue;
        //下一层递归
        backtracking(函数参数);
        回溯过程;
    }
}