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.
Ensure that numbers within the set are sorted in ascending order.
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]]
解题思路：
偷懒一点，直接在Java for LeetCode 040 Combination Sum II上面再加一个depth即可，JAVA实现如下：
public List<List<Integer>> combinationSum3(int k, int n) {
int[] candidates = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
ArrayList<List<Integer>> list = new ArrayList<List<Integer>>();
if (k > 9 || n > 55 || n / k == 0)
return list;
dfs(list, candidates, 0, n, 0, k, 0);
return list;
}
static List<Integer> list2 = new ArrayList<Integer>();
static void dfs(ArrayList<List<Integer>> list, int[] array, int result,
int target, int depth, int k, int depth2) {
if (result == target && depth2 == k) {
list.add(new ArrayList<Integer>(list2));
return;
} else if (depth2 >= k || result > target || depth >= array.length)
return;
for (int i = 0; i <= 1; i++) {
for (int j = 0; j < i; j++) {
list2.add(array[depth]);
depth2++;
}
dfs(list, array, result + array[depth] * i, target, depth + 1, k,
depth2);
for (int j = 0; j < i; j++) {
list2.remove(list2.size() - 1);
depth2--;
}
}
}