002.组合总和|||——回溯算法

1.题目链接：

216. 组合总和 III

2.解题思路：

2.1.题目要求：

给一个元素数量k和一个元素和n，要求从范围[1,2,3,4,5,6,7,8,9]中返回所有元素数量为k和元素和为n的组合。（每个数字只能使用一次）

比如输入k=3，n=7，得[1,2,4]

2.2.思路：

模拟成一个n叉树，用for循环里递归的方式，完成层层遍历，终止条件变成满足元素数量为k和元素和为n就返回就好了。

2.3.回溯三部曲：

2.3.1.确定递归函数参数

需要一维数组path来存放符合条件的结果，二维数组result来存放结果集。

1.  
   vector<vector<int>> result; // 存放结果集
2.  
   vector<int> path; // 符合条件的结果

接下来还需要如下参数：

• targetSum（int）目标和，也就是题目中的n。
• k（int）就是题目中要求k个数的集合。
• sum（int）sum在单层搜索中可以积攒path的和，用于终止条件和targetSun作对比，看看满不满足条件
• startIndex（int）为下一层for循环搜索的起始位置。

1.  
   vector<vector<int>> result;
2.  
   vector<int> path;
3.  
   void backtracking(int targetSum, int k, int sum, int startIndex)

2.3.2.确定终止条件

满足元素数量为k和元素和为n就返回，这里有个隐藏起来的操作，sum不等于targeSum会直接返回。

1.  
   if (path.size() == k) {
2.  
   if (sum == targetSum) result.push_back(path);
3.  
   return; // 如果path.size() == k 但sum != targetSum 直接返回
4.  
   }

2.3.3.单层搜索的过程

单层搜索，for里面套递归，遍历每一条路径（如下“2.2.思路”下面图片的红色箭头），在递归路径的途中用sum搜集path上每一段的值，用于终止条件。

1.  
   for (int i = startIndex; i <= 9; i ) {
2.  
   sum = i;
3.  
   path.push_back(i);
4.  
   backtracking(targetSum, k, sum, i 1); // 注意i 1调整startIndex
5.  
   sum -= i; // 回溯
6.  
   path.pop_back(); // 回溯
7.  
   }

2.4.总代码：

1.  
   class Solution {
2.  
   private:
3.  
   vector<vector<int>> result; // 存放结果集
4.  
   vector<int> path; // 符合条件的结果
5.  
   // targetSum：目标和，也就是题目中的n。
6.  
   // k：题目中要求k个数的集合。
7.  
   // sum：已经收集的元素的总和，也就是path里元素的总和。
8.  
   // startIndex：下一层for循环搜索的起始位置。
9.  
   void backtracking(int targetSum, int k, int sum, int startIndex) {
10.  
    if (path.size() == k) {
11.  
    if (sum == targetSum) result.push_back(path);
12.  
    return; // 如果path.size() == k 但sum != targetSum 直接返回
13.  
    }
14.  
    for (int i = startIndex; i <= 9; i ) {
15.  
    sum = i; // 处理
16.  
    path.push_back(i); // 处理
17.  
    backtracking(targetSum, k, sum, i 1); // 注意i 1调整startIndex
18.  
    sum -= i; // 回溯
19.  
    path.pop_back(); // 回溯
20.  
    }
21.  
    }
22.  
     
23.  
    public:
24.  
    vector<vector<int>> combinationSum3(int k, int n) {
25.  
    result.clear(); // 可以不加
26.  
    path.clear(); // 可以不加
27.  
    backtracking(n, k, 0, 1);
28.  
    return result;
29.  
    }
30.  
    };

3.剪枝优化

3.3.思路：

3.3.1.总和大于n剪枝。

已选元素总和如果已经大于n了，那么往后遍历就没有意义了，直接剪掉。（在终止条件那加上）

 代码如下：

1.  
   if (sum > targetSum) { // 剪枝操作
2.  
   return;
3.  
   }

3.3.2.已选元素数量 可选元素数量 < 题目需要的元素数量 k 剪枝。

代码如下：

for (int i = startIndex; i <= n - (k - path.size())   1; i  ) { // 优化的地方

 （忘记怎么来的可以去001.组合看）

4.记录：

不该早上开游戏的，一出现事情很消耗精力，休息时间再回复消息（除非我去问的），不然老是分心。

这篇好文章是转载于：学新通技术网