CombinationSumII.java

import java.util.ArrayList;
import java.util.List;

public class CombinationSumII {

 /**
 *
 * Given a collection of candidate numbers (candidates) and a target number (target),
 * find all unique combinations in candidates where the candidate numbers sums to target.

 Each number in candidates may only be used once in the combination.

 Note:

 All numbers (including target) will be positive integers.
 The solution set must not contain duplicate combinations.

 Time: O(2^n)
 space: O(n)
 */

 public List<List<Integer>> combinationSum2(int[] candidates, int target) {
 List<List<Integer>> res = new ArrayList<List<Integer>>();
 helper(candidates, target, 0, new ArrayList<>(), res, 0);
 return res;
 }

 public void helper(int[] candidates, int target, int cur, List<Integer> list, List<List<Integer>> res, int sum) {
 if(sum == target) {
 res.add(new ArrayList<>(list));
 return;
 }

 if(sum < target) {
 for(int i = cur; i < candidates.length; i++) {
 if(i != cur && candidates[i] == candidates[i - 1]) continue;
 //When it goes to next level, it could have duplicates, but not in the same level!!
 sum += candidates[i];
 list.add(candidates[i]);

 helper(candidates, target, i + 1, list, res, sum);

 list.remove(list.size() - 1);
 sum -= candidates[i];
 }
 }
 }

 public static void main(String[] args) {
 CombinationSumII a = new CombinationSumII();
 int[] b = {10,1,2,7,6,1,5};
 System.out.println(a.combinationSum2(b,8));
 }
}