My code:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
if (k <= 0 || k > 9 || n <= 0)
return result;
ArrayList<Integer> combination = new ArrayList<Integer>();
getCombinations(1, 1, k, 0, n, combination, result);
return result;
}
private void getCombinations(int begin, int count, int k, int sum, int n,
ArrayList<Integer> combination, ArrayList<List<Integer>> result) {
if (count > k)
return;
else {
for (int i = begin; i <= 9; i++) {
int temp = sum + i;
if (temp > n)
break;
else if (temp == n) {
if (count < k)
break;
else {
combination.add(i);
result.add(new ArrayList<Integer>(combination));
combination.remove(combination.size() - 1);
break;
}
}
else {
combination.add(i);
getCombinations(i + 1, count + 1, k, temp, n, combination, result);
combination.remove(combination.size() - 1);
}
}
}
}
}
My test result:
Paste_Image.png
還是差不多的思路插掂。然后需要限定長度是k妄呕,所以加了一個(gè)統(tǒng)計(jì)個(gè)數(shù)的count
**
總結(jié): Array傀履, DFS
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
ArrayList<List<Integer>> ret = new ArrayList<List<Integer>>();
if (k < 1 || n < 1)
return ret;
ArrayList<Integer> group = new ArrayList<Integer>();
helper(1, 0, 0, k, n, ret, group);
return ret;
}
private void helper(int begin, int sum, int numbers, int k, int n,
ArrayList<List<Integer>> ret, ArrayList<Integer> group) {
if (numbers >= k) { // if numbers == k, then detect whether sum == n
if (sum != n) {
return;
}
else {
ret.add(new ArrayList<Integer>(group));
return;
}
}
else if (sum >= n) // if numbers < k and sum >= n, then return without consideration of sum
return;
else { // if numbers < k and sum < n, then explore it with dfs
for (int i = begin; i < 10; i++) {
group.add(i);
helper(i + 1, sum + i, numbers + 1, k, n, ret, group);
group.remove(group.size() - 1);
}
}
}
}
感覺我這次寫的邏輯更加清晰鸥鹉。沒什么難度搀玖。
Anyway, Good luck, Richardo!