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:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
Solution:
public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> ans = new ArrayList<>();
combinationSum3(ans, k, n, 1, new ArrayList<Integer>());
return ans;
}
public void combinationSum3(List<List<Integer>> ans, int k, int target, int start, List<Integer> list){
if(list.size()==k && target==0){
ans.add(new ArrayList<>(list));
return;
}
for(int i=start; i<=9; i++){
if(target-i<0) break;
list.add(i);
combinationSum3(ans, k, target-i, i+1, list);
list.remove(list.size()-1);
}
}
}