LeetCode程序员面试金典：组合总和 II

　　题目：

　　给定候选人编号的集合candidates和目标数字target，找出candidates中所有可以使数字和target的组合。

　　candidates中的每个数字只能在每个组合中使用一次。

　　注：解集不能包含重复组合。

　　示例1:[10，1，2，7，6，1，5]

　　示例2: 输入: candidates = [2，5，2，1，2]， target = 5.输出:[1，2，2]，[5]]

　　代码实现： class Solution { List freq = new ArrayList(); List> ans = new ArrayList>(); List sequence = new ArrayList(); public List> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); for (int num : candidates) { int size = freq.size(); if (freq.isEmpty() || num != freq.get(size - 1)[0]) { freq.add(new int[]{num, 1}); } else { ++freq.get(size - 1)[1]; } } dfs(0, target); return ans; } public void dfs(int pos, int rest) { if (rest == 0) { ans.add(new ArrayList(sequence)); return; } if (pos == freq.size() || rest < freq.get(pos)[0]) { return; } dfs(pos + 1, rest); int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]); for (int i = 1; i <= most; ++i) { sequence.add(freq.get(pos)[0]); dfs(pos + 1, rest - i * freq.get(pos)[0]); } for (int i = 1; i <= most; ++i) { sequence.remove(sequence.size() - 1); } }}