leetcode 216 Combination Sum III
z
 2018-03-11 11:25:26  

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.

*Example 1:*

Input: *k* = 3, *n* = 7

Output:

1
2
[[1,2,4]]

*Example 2:*

Input: *k* = 3, *n* = 9

Output:

1
[[1,2,6], [1,3,5], [2,3,4]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if(k == 0 || n == 0) return ans;
        backtrace(ans, new ArrayList<Integer>(), k, n, 1);
        return ans;
    }
    public void backtrace(List<List<Integer>> ans, ArrayList<Integer> t, int k, int n, int start){
        if(t.size() == k && n == 0){
            ans.add(new ArrayList<Integer>(t));
            return ;
        }
        for(int j = start; j<=9; j++){
            if(j > n)
                continue;
            t.add(j);
            backtrace(ans, t, k, n-j, j+1);
            t.remove(t.size()-1);
        }
    }
}
  • 注意只能用1-9里面的数字。
  • 注意backtrace的条件里面，j+1，start+1 的区别
    • j+1没有重复数字
    • start+1会有重复数字