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]
题目大意：跟上一题类似，但是有点区别就是候选集中的元素只能出现一次。
解题思路：每次从当前元素的下一个开始计算sum，并把candidate加入List，并且跳过重复元素。
public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<List<Integer>> res = new ArrayList<>(); if (candidates == null || candidates.length == 0) { return res; } Deque<Integer> tmp = new ArrayDeque<>(); Arrays.sort(candidates); helper(res, tmp, 0, target, candidates); return res; } private void helper(List<List<Integer>> res, Deque<Integer> tmp, int start, int target, int[] candidate) { if (target == 0) { res.add(new ArrayList<>(tmp)); // System.out.println(tmp); return; } for (int i = start; i < candidate.length && target >= candidate[i]; i++) { tmp.addLast(candidate[i]); helper(res, tmp, i + 1, target - candidate[i], candidate); tmp.removeLast(); while (i < candidate.length - 1 && candidate[i + 1] == candidate[i]) { i++; } } }
Combination Sum II —— LeetCode
原文：http://www.cnblogs.com/aboutblank/p/4538784.html