# 题目

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]

示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

216. 组合总和 III - 力扣（LeetCode）

# 分析

深度为 k 的 9 叉树

递归三部曲

1 确定递归函数参数：

全局变量路径 path 和结果集 result，

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

2 终止条件

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

3 单层搜索过程

从 1 到 9 循环

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

完整代码

	class Solution {
	private:
	vector<vector<int>> result; // 存放结果集
	vector<int> path; // 符合条件的结果
	//targetSum：目标和，也就是题目中的 n。
	//k：题目中要求 k 个数的集合。
	//sum：已经收集的元素的总和，也就是 path 里元素的总和。
	//startIndex：下一层 for 循环搜索的起始位置。
	void backtracking(int targetSum, int k, int sum, int startIndex) {
	if (path.size() == k) {
	if (sum == targetSum) result.push_back(path);
	return; // 如果 path.size () == k 但 sum != targetSum 直接返回
	}
	for (int i = startIndex; i <= 9; i++) {
	sum += i; // 处理
	path.push_back(i); // 处理
	backtracking(targetSum, k, sum, i + 1); // 注意 i+1 调整 startIndex
	sum -= i; // 回溯
	path.pop_back(); // 回溯
	}
	}

	public:
	vector<vector<int>> combinationSum3(int k, int n) {
	result.clear(); // 可以不加
	path.clear(); // 可以不加
	backtracking(n, k, 0, 1);
	return result;
	}
	};

剪枝

	class Solution {
	private:
	vector<vector<int>> result; // 存放结果集
	vector<int> path; // 符合条件的结果
	void backtracking(int targetSum, int k, int sum, int startIndex) {
	if (sum > targetSum) { // 剪枝操作
	return; // 如果 path.size () == k 但 sum != targetSum 直接返回
	}
	if (path.size() == k) {
	if (sum == targetSum) result.push_back(path);
	return;
	}
	for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝
	sum += i; // 处理
	path.push_back(i); // 处理
	backtracking(targetSum, k, sum, i + 1); // 注意 i+1 调整 startIndex
	sum -= i; // 回溯
	path.pop_back(); // 回溯
	}
	}

	public:
	vector<vector<int>> combinationSum3(int k, int n) {
	result.clear(); // 可以不加
	path.clear(); // 可以不加
	backtracking(n, k, 0, 1);
	return result;
	}
	};

回溯