一、回溯算法模板

  1. void backtracking(参数) {
  2.     if (终止条件) {
  3.         存放结果;
  4.         return;
  5.     }
  7.     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
  8.         处理节点;
  9.         backtracking(路径，选择列表); // 递归
  10.         回溯，撤销处理结果
  11.     }
  12. }

三部曲步骤：

  1. backtracking函数的参数和返回值
  2. 递归的终止条件
  3. 单层的处理逻辑

    二、重点题目总结

    2.1 77. 组合

    该题目是第一道入门的回溯题目 ```cpp class Solution { private: vector> result; // 存放符合条件结果的集合 vector path; // 用来存放符合条件结果 void backtracking(int n, int k, int startIndex) {
    1.  if (path.size() == k) {
    2.      result.push_back(path);
    3.      return;
    4.  }
    5.  for (int i = startIndex; i <= n; i++) {
    6.      path.push_back(i); // 处理节点
    7.      backtracking(n, k, i + 1); // 递归
    8.      path.pop_back(); // 回溯，撤销处理的节点
    9.  }
    } public: vector> combine(int n, int k) {
    1.  result.clear(); // 可以不写
    2.  path.clear();   // 可以不写
    3.  backtracking(n, k, 1);
    4.  return result;
    } };

重点关注startIndex和递归终止条件的处理

该题目可以剪枝：i <= n - (k - path.size()) + 1

  1. <a name="mB0fL"></a>
  2. #### 2.2 216.组合总和III
  3. > 该题目增加了一个限制条件，相加之和为n 且 长度为k
  5. ```cpp
  6. if (path.size() == k) {
  7.     if (sum == targetSum) result.push_back(path);
  8.     return; // 如果path.size() == k 但sum != targetSum 直接返回
  9. }
  11. // 增加一个sum参数记录目前path中的总和。
  12. // 当然可以每次用target - i，终止条件判断target是否为0。
  13. sum += i;
  14. path.push_back(i);
  16. // 这里的两个if条件句不能用&&合并，仔细体会，不然递归函数可能无法终止

2.3 17.电话号码的字母组合

这道题目主要复杂在于：待选集合有多个

leetcode代码

  1. // 设置一个数组记录
  2. const string keyMap[10] = {" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
  4. // 其他部分大差不差
  6. //输入参数i来获取按键的位置索引，再根据i获取数组中的index，根据index去取字母
  7. int index = digits[i] - '0';

2.4 39. 组合总和

candidates 中的数字可以无限制重复被选取，那么把”终止条件“和startIndex修改一下

  1. // 把sum作为终止条件
  2. if (sum > target) return;
  3. else if (sum == target) {
  4.     ans.push_back(path);
  5.     return;
  6. }
  8. for (int i = startIndex; i < candidates.size(); i++) {
  9.     ...
  10.     backtracking(candidates, target, sum, i);  // 下一个递归的起始位置跟当前一样，也就是说当前元素可以重复
  11.     ...
  12. }

2.5 40. 组合总和 II

candidates中有重复元素，因此按照之前的做法会出现重复的结果。如下 image.png 那么重点在于如何去重？ 答：需要对数组排序，增加一个used数组

  1. class Solution {
  2. private:
  3.     vector<int> path;
  4.     vector<vector<int>> ans;
  5.     void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
  6.         if (sum > target) return;
  7.         else if (sum == target) {
  8.             ans.push_back(path);
  9.             return;
  10.         }
  12.         for (int i = startIndex; i < candidates.size(); i++) {
  13.             // 下面的if条件判断用来去重，“当有重复元素且前一个没有使用时，说明这种情况之前已经遍历过了”
  14.             if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
  15.                 continue;
  16.             }
  17.             path.push_back(candidates[i]);
  18.             sum += candidates[i];
  19.             used[i] = true; // 设置是否使用标志位
  20.             backtracking(candidates, target, sum, i + 1, used);
  21.             path.pop_back();
  22.             sum -= candidates[i];
  23.             used[i] = false;
  24.         }
  25.     }
  26. public:
  27.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
  28.         vector<bool> used(candidates.size(), false);  // 排序
  29.         sort(candidates.begin(), candidates.end());
  31.         backtracking(candidates, target, 0, 0, used);
  32.         return ans;
  33.     }
  34. };