ind 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]]
Use recursion, or DFS
One syntax to notice is line 3:
List<List<Integer>> res = new ArrayList<List<Integer>>();
List is abstract and can not be instantiated
1 public class Solution { 2 public List<List<Integer>> combinationSum3(int k, int n) { 3 List<List<Integer>> res = new ArrayList<List<Integer>>(); 4 List<Integer> item = new ArrayList<Integer>(); 5 helper(res, item, k, n, 1); 6 return res; 7 } 8 9 public void helper(List<List<Integer>> res, List<Integer> item, int num, int remain, int start) { 10 if (remain < 0) return; 11 if (num == 0) { 12 if (remain == 0) { 13 res.add(new ArrayList<Integer>(item)); 14 } 15 return; 16 } 17 for (int i=start; i<=9; i++) { 18 item.add(i); 19 helper(res, item, num-1, remain-i, i+1); 20 item.remove(item.size()-1); 21 } 22 } 23 }