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:
*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 { 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 的区别
近期评论