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]]
题目链接：https://leetcode-cn.com/problems/combination-sum-iii/
思路
法一：回溯法
和其他回溯法的题目做法类似，向下传递结果。
剪枝：因为是组合，且每个数只能用一次，则下一层迭代从上次取的数字之后开始。
终止条件是k==0（也可以是k==1）。
小坑：组合中的数字在[1,9]范围内。
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> combinationSum3(int k, int n) {
if(k<=0 || n<=0 || n<k) return res;
vector<int> cur;
trace(k, n, 0, cur);
return res;
}
void trace(int k, int n, int last, vector<int> &cur){
if(k==0){
if(n==0) res.push_back(cur);
return;
}
for(int i = last+1; i<=9; ++i){
if(i>n) break;
cur.push_back(i);
trace(k-1, n-i, i, cur);
cur.pop_back();
}
return;
}
};