|
1 | | -#第216题. 组合总和 III |
2 | | -找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。 |
| 1 | +##链接 |
| 2 | +https://leetcode-cn.com/problems/combination-sum-iii/ |
| 3 | + |
| 4 | +>别看本篇选的是组合总和III，而不是组合总和，本题和上一篇[回溯算法：求组合问题！](https://mp.weixin.qq.com/s/OnBjbLzuipWz_u4QfmgcqQ)相比难度刚刚好！ |
3 | 5 |
|
4 | | -说明： |
| 6 | +#第216题.组合总和III |
5 | 7 |
|
6 | | -所有数字都是正整数。 |
7 | | -解集不能包含重复的组合。 |
| 8 | +链接：https://leetcode-cn.com/problems/combination-sum-iii/ |
8 | 9 |
|
9 | | -示例 1: |
| 10 | +找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。 |
10 | 11 |
|
11 | | -输入: k = 3, n = 7 |
12 | | -输出:[[1,2,4]] |
13 | | -示例 2: |
| 12 | +说明： |
| 13 | +* 所有数字都是正整数。 |
| 14 | +* 解集不能包含重复的组合。 |
14 | 15 |
|
15 | | -输入: k = 3, n = 9 |
16 | | -输出:[[1,2,6],[1,3,5],[2,3,4]] |
| 16 | +示例 1: |
| 17 | +输入: k = 3, n = 7 |
| 18 | +输出:[[1,2,4]] |
| 19 | + |
| 20 | +示例 2: |
| 21 | +输入: k = 3, n = 9 |
| 22 | +输出:[[1,2,6],[1,3,5],[2,3,4]] |
17 | 23 |
|
18 | 24 |
|
19 | 25 | #思路 |
20 | 26 |
|
21 | | -这道题目注意一下几点： |
| 27 | +本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。 |
| 28 | + |
| 29 | +相对于[回溯算法：求组合问题！](https://mp.weixin.qq.com/s/OnBjbLzuipWz_u4QfmgcqQ)，无非就是多了一个限制，本题是要找到和为n的k个数的组合，而整个集合已经是固定的了[1,...,9]。 |
22 | 30 |
|
23 | | -* 解集不能包含重复的组合。 说明不用去重了，难度就小一些。 |
24 | | -* 求的是组合，那么集合没有顺序，for里面依然要从startIndex开始（如果是排列的话，就从0开始） |
| 31 | +想到这一点了，做过[77. 组合](https://mp.weixin.qq.com/s/OnBjbLzuipWz_u4QfmgcqQ)之后，本题是简单一些了。 |
25 | 32 |
|
26 | | -本题k相当于限制了树的深度，9就是树的宽度。 |
| 33 | +本题k相当于了树的深度，9（因为整个集合就是9个数）就是树的宽度。 |
| 34 | + |
| 35 | +例如 k = 2，n = 4的话，就是在集合[1,2,3,4,5,6,7,8,9]中求 k（个数） = 2, n（和） = 4的组合。 |
27 | 36 |
|
28 | 37 | 选取过程如图： |
29 | 38 |
|
30 | 39 | <imgsrc='../pics/216.组合总和III.png'width=600> </img></div> |
31 | 40 |
|
32 | | -那么这还是一道标准的模板题，模板： |
| 41 | +图中，可以看出，只有最后取到集合（1，3）和为4 符合条件。 |
| 42 | + |
| 43 | + |
| 44 | +##回溯三部曲 |
| 45 | + |
| 46 | +***确定递归函数参数** |
| 47 | + |
| 48 | +和[回溯算法：求组合问题！](https://mp.weixin.qq.com/s/OnBjbLzuipWz_u4QfmgcqQ)一样，依然需要一维数组path来存放符合条件的结果，二维数组result来存放结果集。 |
| 49 | + |
| 50 | +这里我依然定义path 和 result为全局变量。 |
| 51 | + |
| 52 | +至于为什么取名为path？从上面树形结构中，可以看出，结果其实就是一条根节点到叶子节点的路径。 |
| 53 | + |
| 54 | +``` |
| 55 | +vector<vector<int>> result; // 存放结果集 |
| 56 | +vector<int> path; // 符合条件的结果 |
| 57 | +``` |
| 58 | + |
| 59 | +接下来还需要如下参数： |
| 60 | + |
| 61 | +* targetSum（int）目标和，也就是题目中的n。 |
| 62 | +* k（int）就是题目中要求k个数的集合。 |
| 63 | +* sum（int）为已经收集的元素的总和，也就是path里元素的总和。 |
| 64 | +* startIndex（int）为下一层for循环搜索的起始位置。 |
| 65 | + |
| 66 | +所以代码如下： |
33 | 67 |
|
34 | 68 | ``` |
35 | | -backtracking() { |
36 | | - if (终止条件) { |
37 | | - 存放结果; |
| 69 | +vector<vector<int>> result; |
| 70 | +vector<int> path; |
| 71 | +void backtracking(int targetSum, int k, int sum, int startIndex) |
| 72 | +``` |
| 73 | +其实这里sum这个参数也可以省略，每次targetSum减去选取的元素数值，然后判断如果targetSum为0了，说明收集到符合条件的结果了，我这里为了直观便于理解，还是加一个sum参数。 |
| 74 | + |
| 75 | +还要强调一下，回溯法中递归函数参数很难一次性确定下来，一般先写逻辑，需要啥参数了，填什么参数。 |
| 76 | + |
| 77 | +* 确定终止条件 |
| 78 | + |
| 79 | +什么时候终止呢？ |
| 80 | + |
| 81 | +在上面已经说了，k其实就已经限制树的深度，因为就取k个元素，树再往下深了没有意义。 |
| 82 | + |
| 83 | +所以如果path.size() 和 k相等了，就终止。 |
| 84 | + |
| 85 | +如果此时path里收集到的元素和（sum） 和targetSum（就是题目描述的n）相同了，就用result收集当前的结果。 |
| 86 | + |
| 87 | +所以 终止代码如下： |
| 88 | + |
| 89 | +``` |
| 90 | +if (path.size() == k) { |
| 91 | + if (sum == targetSum) result.push_back(path); |
| 92 | + return; // 如果path.size() == k 但sum != targetSum 直接返回 |
| 93 | +} |
| 94 | +``` |
| 95 | + |
| 96 | +***单层搜索过程** |
| 97 | + |
| 98 | +本题和[回溯算法：求组合问题！](https://mp.weixin.qq.com/s/OnBjbLzuipWz_u4QfmgcqQ)区别之一就是集合固定的就是9个数[1,...,9]，所以for循环固定i<=9 |
| 99 | + |
| 100 | +如图： |
| 101 | +<imgsrc='../pics/216.组合总和III.png'width=600> </img></div> |
| 102 | + |
| 103 | +处理过程就是 path收集每次选取的元素，相当于树型结构里的边，sum来统计path里元素的总和。 |
| 104 | + |
| 105 | +代码如下： |
| 106 | + |
| 107 | +``` |
| 108 | +for (int i = startIndex; i <= 9; i++) { |
| 109 | + sum += i; |
| 110 | + path.push_back(i); |
| 111 | + backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex |
| 112 | + sum -= i; // 回溯 |
| 113 | + path.pop_back(); // 回溯 |
| 114 | +} |
| 115 | +``` |
| 116 | + |
| 117 | +**别忘了处理过程 和 回溯过程是一一对应的，处理有加，回溯就要有减！** |
| 118 | + |
| 119 | +参照[关于回溯算法，你该了解这些！](https://mp.weixin.qq.com/s/gjSgJbNbd1eAA5WkA-HeWw)中的模板，不难写出如下C++代码： |
| 120 | + |
| 121 | +``` |
| 122 | +class Solution { |
| 123 | +private: |
| 124 | + vector<vector<int>> result; // 存放结果集 |
| 125 | + vector<int> path; // 符合条件的结果 |
| 126 | + // targetSum：目标和，也就是题目中的n。 |
| 127 | + // k：题目中要求k个数的集合。 |
| 128 | + // sum：已经收集的元素的总和，也就是path里元素的总和。 |
| 129 | + // startIndex：下一层for循环搜索的起始位置。 |
| 130 | + void backtracking(int targetSum, int k, int sum, int startIndex) { |
| 131 | + if (path.size() == k) { |
| 132 | + if (sum == targetSum) result.push_back(path); |
| 133 | + return; // 如果path.size() == k 但sum != targetSum 直接返回 |
| 134 | + } |
| 135 | + for (int i = startIndex; i <= 9; i++) { |
| 136 | + sum += i; // 处理 |
| 137 | + path.push_back(i); // 处理 |
| 138 | + backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex |
| 139 | + sum -= i; // 回溯 |
| 140 | + path.pop_back(); // 回溯 |
| 141 | + } |
38 | 142 | } |
39 | 143 |
|
40 | | - for (选择：选择列表（可以想成树中节点孩子的数量）) { |
41 | | - 递归，处理节点; |
42 | | - backtracking(); |
43 | | - 回溯，撤销处理结果 |
| 144 | +public: |
| 145 | + vector<vector<int>> combinationSum3(int k, int n) { |
| 146 | + result.clear(); // 可以不加 |
| 147 | + path.clear(); // 可以不加 |
| 148 | + backtracking(n, k, 0, 1); |
| 149 | + return result; |
44 | 150 | } |
45 | | -} |
| 151 | +}; |
46 | 152 | ``` |
47 | 153 |
|
| 154 | +##剪枝 |
| 155 | + |
| 156 | +这道题目，剪枝操作其实是很容易想到了，想必大家看上面的树形图的时候已经想到了。 |
| 157 | + |
| 158 | +如图： |
| 159 | +<imgsrc='../pics/216.组合总和III1.png'width=600> </img></div> |
| 160 | + |
| 161 | +已选元素总和如果已经大于n（图中数值为4）了，那么往后遍历就没有意义了，直接剪掉。 |
48 | 162 |
|
| 163 | +那么剪枝的地方一定是在递归终止的地方剪，剪枝代码如下： |
| 164 | + |
| 165 | +``` |
| 166 | +if (sum > targetSum) { // 剪枝操作 |
| 167 | + return; |
| 168 | +} |
| 169 | +``` |
49 | 170 |
|
50 | | -#C++代码 |
| 171 | +最后C++代码如下： |
51 | 172 |
|
52 | 173 | ``` |
53 | 174 | class Solution { |
54 | 175 | private: |
55 | | - vector<vector<int>> result; |
56 | | - vector<int> path; |
57 | | - void backtracking(int target, int k, int num, int sum, int startIndex) { |
58 | | - if (sum > target || num > k) { // 剪枝操作，如果sum大于target或者num大于k了没有继续搜索的必要了 |
59 | | - return; |
| 176 | + vector<vector<int>> result; // 存放结果集 |
| 177 | + vector<int> path; // 符合条件的结果 |
| 178 | + // targetSum：目标和，也就是题目中的n。 |
| 179 | + // k：题目中要求k个数的集合。 |
| 180 | + // sum：已经收集的元素的总和，也就是path里元素的总和。 |
| 181 | + // startIndex：下一层for循环搜索的起始位置。 |
| 182 | + void backtracking(int targetSum, int k, int sum, int startIndex) { |
| 183 | + if (sum > targetSum) { // 剪枝操作 |
| 184 | + return; // 如果path.size() == k 但sum != targetSum 直接返回 |
60 | 185 | } |
61 | | - if (num == k && sum == target) { |
62 | | - result.push_back(path); |
| 186 | + if (path.size() == k) { |
| 187 | +if (sum == targetSum)result.push_back(path); |
63 | 188 | return; |
64 | 189 | } |
65 | | -
|
66 | 190 | for (int i = startIndex; i <= 9; i++) { |
67 | | - sum += i; |
68 | | - path.push_back(i); |
69 | | - num++; |
70 | | - backtracking(target, k, num, sum, i + 1); |
71 | | - num--; |
72 | | - sum -= i; |
73 | | - path.pop_back(); |
| 191 | + sum += i; // 处理 |
| 192 | + path.push_back(i); // 处理 |
| 193 | + backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex |
| 194 | + sum -= i; // 回溯 |
| 195 | + path.pop_back(); // 回溯 |
74 | 196 | } |
75 | 197 | } |
76 | 198 |
|
77 | 199 | public: |
78 | 200 | vector<vector<int>> combinationSum3(int k, int n) { |
79 | | - backtracking(n, k, 0, 0, 1); |
| 201 | + result.clear(); // 可以不加 |
| 202 | + path.clear(); // 可以不加 |
| 203 | + backtracking(n, k, 0, 1); |
80 | 204 | return result; |
81 | | -
|
82 | 205 | } |
83 | 206 | }; |
84 | 207 | ``` |
| 208 | + |
| 209 | +#总结 |
| 210 | + |
| 211 | +开篇就介绍了本题与[回溯算法：求组合问题！](https://mp.weixin.qq.com/s/OnBjbLzuipWz_u4QfmgcqQ)的区别，相对来说加了元素总和的限制，如果做完[回溯算法：求组合问题！](https://mp.weixin.qq.com/s/OnBjbLzuipWz_u4QfmgcqQ)再做本题在合适不过。 |
| 212 | + |
| 213 | +分析完区别，依然把问题抽象为树形结构，按照回溯三部曲进行讲解，最后给出剪枝的优化。 |
| 214 | + |
| 215 | +相信做完本题，大家对组合问题应该有初步了解了。 |
| 216 | + |
| 217 | +**就酱，如果感觉对你有帮助，就帮Carl转发一下吧，让更多小伙伴知道这里！** |