力扣-216-组合总和Ⅲ

仍旧是有一个目标和，但是另一个条件变了

• 从给定的数组元素中选择变成了从1-9中固定选择
• 不限结果数组元素个数变成了限制k个数字

（看起来有点像组合的加强版）
从1-9中选择k个数字组合，使得他们的和=n

嗯…那我不是对组合的结果筛一筛既可以了？！

class Solution {
public:
	vector<vector<int>> res;
	vector<int> temp;
	vector<vector<int>> combinationSum3(int k, int n) {
		backTrack(k, n, 1);
		return res;
	}

	void backTrack(int k,int n,int cur) {
		if (temp.size() == k && accumulate(temp.begin(), temp.end(), 0) == n) {
			res.push_back(temp);
			return;
		}
		for (int i = cur; i <= 9; i++) {
			temp.push_back(i);
			backTrack(k, n, i + 1);
			temp.pop_back();
		}
	}
};

当然直接调函数是最快的，也是思路最清晰的，但是不是效率最高的，因为它计算了所有的组合
所以我们尝试优化一下，其实就是之前的老办法

class Solution {
public:
	vector<vector<int>> res;
	vector<int> temp;
	vector<vector<int>> combinationSum3(int k, int n) {
		backTrack(k, n, 1);
		return res;
	}

	void backTrack(int k,int target,int cur) {
		if (target < 0) return;
		if (temp.size() == k && target==0) {
			res.push_back(temp);
			return;
		}
		for (int i = cur; i <= 9; i++) {
			temp.push_back(i);
			backTrack(k, target-i, i + 1);
			temp.pop_back();
		}
	}
};