216. Combination Sum III

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:

Classic DFS,

Base case:

When  item.size == k and target ==0 , then add the item to the result list.

if item.size==k target!=0 end the recursion

If target <=0 while item.size!=k, end the recursion, because we are only adding positive numbers, any further DFS won't give us the right answer.

  public List<List<Integer>> combinationSum3(int k, int n) {  
     List<List<Integer>> res=new ArrayList<List<Integer>>();  
     List<Integer> item=new ArrayList<Integer>();  
     DFSHelper(res,item,1,k,n);  
     return res;  
   }  
   public void DFSHelper(List<List<Integer>> res, List<Integer> item, int start,int k, int target){  
     if(item.size()==k && target==0){  
       List<Integer> temp=new ArrayList<Integer>(item);  
       res.add(temp);  
       return;  
     }  
     if(item.size()>=k) return;  
     if(target<=0) return;  
     for(int i=start;i<=9;i++){  
       item.add(i);  
       DFSHelper(res,item,i+1,k,target-i);  
       item.remove(item.size()-1);  
     }      
   }