组合综合III

来源Leetcode第216题组合综合III

找出所有相加之和为 n 的 k\ 个数的组合。\组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。

• 解集不能包含重复的组合。

  示例 1:

  输入: k = 3, n = 7
  输出: [[1,2,4]]

---

回溯

List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
    //List<Integer> tmp = new ArrayList<>();
    backtrack(1,n,k,new ArrayList<>());
    return ans;
}

void backtrack(int start,int target ,int k,List<Integer> tmp){
    if(tmp.size() > k || target < 0)
        return;
    if(target == 0 && tmp.size() == k) {
        ans.add(new ArrayList<>(tmp));
        return;
    }
    for(int i = start; i < 10; i++){
        if(target < start)
            break;
        tmp.add(i);
        backtrack(i+1,target-i,k,tmp);
        tmp.remove(tmp.size() - 1);
    }
}