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:
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]
Solution:
1 public class Solution { 2 public List<List<Integer>> combinationSum2(int[] candidates, int target) { 3 List<List<Integer>> result=new ArrayList<List<Integer>>(); 4 List<Integer> al=new ArrayList<Integer>(); 5 Arrays.sort(candidates); 6 dfs(result,al,target,candidates,0); 7 return result; 8 } 9 10 private void dfs(List<List<Integer>> result, List<Integer> al, int target, int[] candidates, int position) { 11 // TODO Auto-generated method stub 12 if(target<0) 13 return; 14 if(target==0){ 15 result.add(new ArrayList<Integer>(al)); 16 return; 17 } 18 for(int i=position;i<candidates.length;++i){ 19 al.add(candidates[i]); 20 dfs(result, al, target-candidates[i], candidates, i+1); 21 al.remove(al.size()-1); 22 while((i+1<candidates.length)&&candidates[i]==candidates[i+1]) 23 ++i; 24 } 25 } 26 }
这道题和Combination Sum那道题很像，区别就是在第20行和第22行，
如果candidates[i]==candidates[i+1]，就直接跳过candidates[i+1]这个选项了，因为不能有重复的solution嘛。
原文：http://www.cnblogs.com/Phoebe815/p/4093961.html