Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

Naive Way: Make a recursive function to DFS on all possible combinations. And sort the entire array at first helps to keep numbers in order.

 public class Solution {  
   public List<List<Integer>> combinationSum(int[] candidates, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Arrays.sort(candidates);  
     dfs(candidates, 0, target, 0, new ArrayList<Integer>(), rslt);  
     return rslt;  
   }  
   private void dfs(int[] n, int index, int target, int sum, List<Integer> path, List<List<Integer>> rslt){  
     // ending case  
     if(sum==target){rslt.add(path); return;}  
     // recursion  
     for(int i = index;i < n.length;i++){  
       if(n[i]+sum > target) break;  
       List<Integer> list = new ArrayList<Integer>(path);  
       list.add(n[i]);  
       dfs(n, i, target, sum+n[i], list, rslt);  
     }  
   }  
 }  

The corresponding iterative way is using a stack to implement DFS.

 public class Solution {  
   class SumNode{  
     int index;  
     int sum;  
     List<Integer> path;  
     SumNode(int index, int value, List<Integer> path){  
       this.index = index;  
       this.sum = value;  
       this.path = new ArrayList<Integer>(path);  
     }  
     public void addNumber(int value){  
       this.sum += value;  
       this.path.add(value);  
     }  
   }  
   public List<List<Integer>> combinationSum(int[] candidates, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Stack<SumNode> stack = new Stack<SumNode>();  
     Arrays.sort(candidates);  
     SumNode root = new SumNode(0, 0, new ArrayList<Integer>());  
     stack.push(root);  
     while(!stack.isEmpty()){  
       SumNode node = stack.pop();  
       for(int i = node.index;i < candidates.length;i++){  
         if(node.sum + candidates[i] > target) break;  
         SumNode child = new SumNode(i, node.sum, node.path);  
         child.addNumber(candidates[i]);  
         if(child.sum==target) rslt.add(child.path);  
         else stack.push(child);  
       }  
     }  
     return rslt;  
   }  
 }  

And I though about it for a while and tried BFS on it. (Just change the stack to queue). It works. DFS and BFS are two traversal methods on this problem.

 public class Solution {  
   class SumNode{  
     int index;  
     int sum;  
     List<Integer> path;  
     SumNode(int index, int value, List<Integer> path){  
       this.index = index;  
       this.sum = value;  
       this.path = new ArrayList<Integer>(path);  
     }  
     public void addNumber(int value){  
       this.sum += value;  
       this.path.add(value);  
     }  
   }  
   public List<List<Integer>> combinationSum(int[] candidates, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Queue<SumNode> queue = new LinkedList<SumNode>();  
     Arrays.sort(candidates);  
     SumNode root = new SumNode(0, 0, new ArrayList<Integer>());  
     queue.add(root);  
     while(!queue.isEmpty()){  
       SumNode node = queue.poll();  
       for(int i = node.index;i < candidates.length;i++){  
         if(node.sum + candidates[i] > target) break;  
         SumNode child = new SumNode(i, node.sum, node.path);  
         child.addNumber(candidates[i]);  
         if(child.sum==target) rslt.add(child.path);  
         else queue.add(child);  
       }  
     }  
     return rslt;  
   }  
 }