https://leetcode.cn/problems/combination-sum-iii/description/

<aside> 💡

与 77. 组合 差不多，就返回条件中收集结果步骤多了一步判断，同时剪枝策略多了一种

</aside>

vector<vector<int>> ans;
vector<int> path;
int sum = 0;

void backtracking(int num, int& k, int& n) {
		if (path.size() == k) {
				if (sum == n)
						ans.push_back(path);
				return;
		}
	
		// 剪枝1：同77.组合
		// 剪枝2：如果当前数已经大于n，那么该循环之后的数必定都大于n，执行剪枝
		for (int i = num; i <= 9 - (k - path.size()) + 1 && sum + i <= n; ++i) {
				sum += i;
				path.push_back(i);
				backtracking(i + 1, k, n);
				sum -= i;
				path.pop_back();
		}
}

vector<vector<int>> combinationSum3(int k, int n) {
		backtracking(1, k, n);
		return ans;
}