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]]

 

Credits:

Special thanks to  for adding this problem and creating all test cases.

 

 to see which companies asked this question

 

1 public class Solution { 2     public List
      
       
        > combinationSum3(int k, int n) { 3         ArrayList
        
         
          > ans = new ArrayList
          
           
            >(); 4 ArrayList
            
              tmp = new ArrayList
             
              (); 5 if(k < 1 || n < 1) return ans; 6 combinationDFS(ans, tmp, k, n, 1, 0); 7 return ans; 8 } 9 10 public void combinationDFS(ArrayList
              
               
                > ans, ArrayList
                
                  tmp, int k, int n, int level, int sum){11 if(sum == n && k == 0){12 ans.add(new ArrayList(tmp));13 return;14 }else if(sum > n || k < 0){15 return;16 }17 for(int i = level; i<=9; i++){18 tmp.add(i);19 combinationDFS(ans,tmp,k-1,n,i+1,sum+i);20 tmp.remove(tmp.size()-1);21 }22 }23 }