Java for LeetCode 216 Combination Sum III

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--;
}
}
}
上一篇:CMS GC启动参数优化配置


下一篇:Java for LeetCode 214 Shortest Palindrome