216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

• All numbers will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]

Example 2:

Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]]

---

从1~9中取k个数，使得这k个数的和等于n，求出所有取数方案。 简单的递归题，为了不重复，每次从上次取数的下一个取，代码如下：

class Solution {
private:
    void dfs(vector<vector<int> >& ans, vector<int>& cand, int step, const int& k, int sum)
    {
        if (cand.size() == k && sum == 0) {
            ans.push_back(cand);
            return;
        }
        for (int i = step; i <= 9; ++i) {
            if (i > sum)
                break;
            cand.push_back(i);
            dfs(ans, cand, i + 1, k, sum – i);
            cand.pop_back();
        }
    }
public:
    vector<vector<int> > combinationSum3(int k, int n)
    {
        vector<vector<int> > ans;
        vector<int> cand;
        dfs(ans, cand, 1, k, n);
        return ans;
    }
};

本代码提交AC，用时3MS。

二刷。代码如下：

class Solution {
	void dfs(vector<vector<int>> &ans, vector<int> &cand, int k, int n, int &sum) {
		if (cand.size() == k && sum == n) {
			ans.push_back(cand);
			return;
		}
		if (cand.size() >= k || sum >= n)return;
		int start = 1;
		if (!cand.empty())start = cand.back() + 1;
		for (int i = start; i <= 9; ++i) {
			cand.push_back(i);
			sum += i;
			dfs(ans, cand, k, n, sum);
			sum -= i;
			cand.pop_back();
		}
	}
public:
	vector<vector<int>> combinationSum3(int k, int n) {
		if (k > 9 || n > 45)return { };
		vector<vector<int>> ans;
		vector<int> cand;
		int sum = 0;
		dfs(ans, cand, k, n, sum);
		return ans;
	}
};

本代码提交AC，用时0MS。