LeetCode-组合总和 III（C++）

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

思路：用回溯算法，定义全局变量result为结果集，path为每次搜索的路径，sum为每次搜索路径的和。

然后回溯三部曲，参数列表为n,k和起始搜索startIndex，没有返回值。

如果sum值大于n，return，结束该条路径的搜索；如果路径长度达到k并且sum等于n，收集结果，并返回。

确定单层搜索逻辑，从startIndex开始搜索，每次sum值加上当前节点值，路径加上当前节点，递归，然后回溯，sum减去当前节点值，路径去掉当前节点。

这里for循环可以做剪枝，i<=9 - (k - path.size()) + 1;路径长度达不到k的，不去遍历。

代码：

class Solution {	//216. 组合总和 III
public:
	vector<vector<int>> result;
	vector<int> path;
	int sum = 0;
	void backtracking(int k, int n, int startIndex) {
		if (sum > n)return;
		if (path.size() == k && sum==n) {
			result.push_back(path);
			return;
		}
		for (int i = startIndex; i <= 9 - (k - path.size()) + 1; ++i) {
			sum += i;
			path.push_back(i);
			backtracking(k, n, i + 1);
			path.pop_back();
			sum -= i;
		}
	}
	vector<vector<int>> combinationSum3(int k, int n) {
		backtracking(k, n, 1);
		return result;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

参考资料：代码随想录