Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
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 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

Naive Way: It's the same with  combination-sum . Just change the iteration index to index+1.

DFS iterative method

 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>> combinationSum2(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     Stack<SumNode> stack = new Stack<SumNode>();  
     Arrays.sort(num);  
     SumNode root = new SumNode(-1, 0, new ArrayList<Integer>());  
     stack.push(root);  
     while(!stack.isEmpty()){  
       SumNode node = stack.pop();  
       for(int i = node.index+1;i < num.length;i++){  
         if(node.sum + num[i] > target) break;  
         SumNode child = new SumNode(i, node.sum, node.path);  
         child.addNumber(num[i]);  
         if(child.sum==target) set.add(child.path);  
         else stack.push(child);  
       }  
     }  
     rslt.addAll(set);  
     return rslt;  
   }  
 }  

BFS iterative method

 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>> combinationSum2(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     Queue<SumNode> queue = new LinkedList<SumNode>();  
     Arrays.sort(num);  
     SumNode root = new SumNode(-1, 0, new ArrayList<Integer>());  
     queue.add(root);  
     while(!queue.isEmpty()){  
       SumNode node = queue.poll();  
       for(int i = node.index+1;i < num.length;i++){  
         if(node.sum + num[i] > target) break;  
         SumNode child = new SumNode(i, node.sum, node.path);  
         child.addNumber(num[i]);  
         if(child.sum==target) set.add(child.path);  
         else queue.add(child);  
       }  
     }  
     rslt.addAll(set);  
     return rslt;  
   }  
 }  

Recursive Method:

 public class Solution {  
   public List<List<Integer>> combinationSum2(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     Arrays.sort(num);   
     dfs(num, -1, target, 0, new ArrayList<Integer>(), set);  
     rslt.addAll(set);  
     return rslt;   
   }  
   private void dfs(int[] n, int index, int target, int sum, List<Integer> path, Set<List<Integer>> set){   
    // ending case   
    if(sum==target){set.add(path); return;}   
    // recursion   
    for(int i = index+1;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, set);   
    }   
   }   
 }  

Notice: Since all the above solution requires sorting at first. The time complexity is O(nlogn). Space is O(n!).

Improved Way: Can I apply iterative method without using extra class (SumNode in the above code).
If I directly use List<Integer> as nodes, I need to find a way to store the sum of the list and the current index.  I could use the first element to store the sum, the second element to store the current index.

 public class Solution {  
   public List<List<Integer>> combinationSum2(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     Stack<List<Integer>> stack = new Stack<List<Integer>>();  
     Arrays.sort(num);  
     // initial list  
     List<Integer> root = new ArrayList<Integer>();  
     root.add(0);  
     root.add(-1);  
     // DFS  
     stack.push(root);  
     while(!stack.isEmpty()){  
       List<Integer> list = stack.pop();  
       // check if target found  
       if(list.get(0)==target){  
         List<Integer> path = new ArrayList<Integer>();  
         for(int i = 0;i < list.size()-2;i++)  
           path.add(list.get(i+2));  
         set.add(path);  
       }  
       // push child list  
       for(int i = list.get(1)+1;i < num.length;i++){  
         if(list.get(0)+num[i] > target) break;  
         List<Integer> path = new ArrayList<Integer>(list);  
         path.set(0, path.get(0)+num[i]);  
         path.set(1, i);  
         path.add(num[i]);  
         stack.push(path);  
       }  
     }  
     rslt.addAll(set);  
     return rslt;   
   }  
 }