public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> ans = new ArrayList<>();
combination(ans, new ArrayList<Integer>(), k, 1, n);
return ans;
}
private void combination(List<List<Integer>> ans, List<Integer> comb, int k, int start, int n) {
if (comb.size() == k && n == 0) {
List<Integer> li = new ArrayList<Integer>(comb);
ans.add(li);
return;
}
for (int i = start; i <= 9; i++) {
comb.add(i);
combination(ans, comb, k, i+1, ni);
comb.remove(comb.size()  1);
}
}
Simple and clean Java code, backtracking.


To make this faster, you can quit the for loop early and avoid unnecessary work.
private static void combination(List<List<Integer>> ans, List<Integer> comb, int k, int start, int n) { if (comb.size() > k) { return; } if (comb.size() == k && n == 0) { List<Integer> li = new ArrayList<Integer>(comb); ans.add(li); return; } for (int i = start; i <= n && i<=9; i++) { comb.add(i); combination(ans, comb, k, i+1, ni); comb.remove(comb.size()  1); } }
if you think for loop with multiple conditions is complex, you can add an if condition inside the for loop instead.
private static void combination(List<List<Integer>> ans, List<Integer> comb, int k, int start, int n) { if (comb.size() > k) { return; } if (comb.size() == k && n == 0) { List<Integer> li = new ArrayList<Integer>(comb); ans.add(li); return; } for (int i = start; i<=9; i++) { if (ni >= 0) { comb.add(i); combination(ans, comb, k, i+1, ni); comb.remove(comb.size()  1); } } }

Great solution! But I still have a question about
List<Integer> li = new ArrayList<Integer>(comb);
Why we can't list.add(comb) directly? I tried that, but the result is wrong.
And I tried ans.addAll(comb), it showed me " no suitable method found for addAll(List<Integer>) " But list indeed has this method. Could you explain that? Thank you so much in advance.


@wwtwxlwjh List<Integer> li = new ArrayList<Integer>(comb) will copy comb to a new memory space. Besides, comb will be modified later. So if you just add comb to list, list will just make a pointer pointing to comb instead of making a new memory space. So if comb is modified, list will be modified too.

@topcoder4309 said in Simple and clean Java code, backtracking.:
if (comb.size() > k) {
return;
}
if (comb.size() == k && n == 0) {
List<Integer> li = new ArrayList<Integer>(comb);
ans.add(li);
return;
}Isn't this better? Reduces one more call.
if (comb.size() == k && n == 0) { List<Integer> li = new ArrayList<Integer>(comb); ans.add(li); return; } else if (comb.size() == k) { return; }

@topcoder4309 In fact we can combine 'if(ni>=0)' with the 'comb.size()>k' in the beginning, and it will become:
private static void combination(List<List<Integer>> ans, List<Integer> comb, int k, int start, int n) {
if (comb.size() > k  n<0) {
return;
}
if (comb.size() == k && n == 0) {
List<Integer> li = new ArrayList<Integer>(comb);
ans.add(li);
return;
}
for (int i = start; i<=9; i++) {
comb.add(i);
combination(ans, comb, k, i+1, ni);
comb.remove(comb.size()  1);
}
}

@chintant I think it is 9 * 8 * ... (9k+1), which is factorial time, because we would try 9i+1 possible numbers in ith step. If I were wrong, please point me out.

@ZhuEason I think it is O(n.2^n), where n is 9, since only numbers from 1 to 9 can be used.
consider if k>=9 then there will be 2^9 times combination method will be called by this code and each combination method takes O(n) time to add the Elements of the comb list. This is the worst time complexity. However I am not able to understand If k is less than 9 then what will be the average time complexity?
Technically you can also argue that since n can never be greater than 9 its time complexity is O(1).

adding the judge of " if (target < 0) return;" should reduce some work in some situation. eg,when n can be summed to with 0ne or two number.
public class Solution { public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> result = new ArrayList<>(); if (k<=0  n <= 0) return result; backTrack(k, n, 1, result, new ArrayList<Integer>()); return result; } private void backTrack(int k, int target, int beginIdx, List<List<Integer>> result, List<Integer> record) { if (target < 0) { return; } if (record.size() == k) { if (target == 0) { result.add(new ArrayList<Integer>(record)); } return; } for (int i=beginIdx; i < 10; i++) { record.add(i); backTrack(k, target  i, i + 1, result, record); record.remove(record.size()  1); } } }