[LeetCode]Combination Sum III

DFS的题，没啥好讲的。时间复杂度O(C(n , k))，空间复杂度O(k)，代码如下：

	class Solution {
	public:
	vector<vector<int>> combinationSum3(int k, int n) {
	vector<vector<int>> res;
	vector<int> curr;
	backtrack(res, curr, 1, k, n, 0);
	return res;
	}
	private:
	void backtrack(vector<vector<int>>& res, vector<int>& curr, int i, int k, int n, int sum)
	{
	if(sum > n)return;
	if(curr.size() == k)
	{
	if(sum == n)
	res.push_back(curr);
	return;
	}
	for(int j = i; j <= 9; ++j)
	{
	curr.push_back(j);
	backtrack(res, curr, j + 1, k, n, sum + j);
	curr.pop_back();
	}
	}
	};

view raw Combination Sum III.cpp hosted with ❤ by GitHub