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

 

 

这道题和combination sum非常像，只是需要注意，这个需要判断是不是重复的，因为input是可能有重复值的。可以用contains来判断是否有重复，但是很慢，比较妙的是添加的时候就判断了。

用contains判断

public class Solution {    List
      
       
        > result;    List
        
          current;    public List
         
          
           > combinationSum2(int[] candidates, int target) {        result = new ArrayList<>();        if (candidates == null || candidates.length == 0) {            return result;        }        current = new ArrayList<>();        Arrays.sort(candidates);        helper(candidates, target, 0);        return result;    }    public void helper(int[] candidates, int target, int start) {        if (target < 0) {            return;        }        if (target == 0) {            List
           
             tmp = new ArrayList<>(current); if (!result.contains(tmp)) { result.add(new ArrayList<>(current)); } return; } for (int i = start; i < candidates.length && target >= candidates[i]; i++) { current.add(candidates[i]); helper(candidates, target - candidates[i], i + 1); current.remove(current.size() - 1); } }}
           
          
         
        
       
      

添加时判断

public class Solution {    List
      
       
        > result;    List
        
          current;    public List
         
          
           > combinationSum2(int[] candidates, int target) {        result = new ArrayList<>();        if (candidates == null || candidates.length == 0) {            return result;        }        current = new ArrayList<>();        Arrays.sort(candidates);        helper(candidates, target, 0);        return result;    }    public void helper(int[] candidates, int target, int start) {        if (target < 0) {            return;        }        if (target == 0) {            List
           
             tmp = new ArrayList<>(current); result.add(new ArrayList<>(current)); return; } for (int i = start; i < candidates.length && target >= candidates[i]; i++) { if (i > start && candidates[i] == candidates[i - 1]) { continue; } current.add(candidates[i]); helper(candidates, target - candidates[i], i + 1); current.remove(current.size() - 1); } }}
           
          
         
        
       
      

需注意这种判断方式不适合可重复取同一个数字的情况（也就是不适合combination sum lintcode)， 因为重复取的时候start一直在左边，所以重复的数字也会被加进去，会导致重复的结果。