原题：
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.
- Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
- 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 非常类似，也是从一组数中找到其和为指定值的所有组合。但是本题的特殊之处在于每个给出的候选数只能用一次，且组合不能重复。
思路：
- 大体思路不变，仍是一个类似深搜的树，只不过原本树的每个节点下的子节点包括自身，而本题的树的每一个节点的子节点是所有排在该节点之后的数，而不包括其本身。如【1，1，2，5，6，7，10】，第一个1的子节点是(1,2,5,6,7,10)，第二个1的子节点是(2,5,6,7,10)。
- 第二个难点在于组合不能重复。譬如仅使用第一个1的组合可以是（1，7），（1，2，5）；而仅使用第二个1的组合也可以是（1，7），（1，2，5）。所以要加入一个判断机制。每当循环走过一个节点，我们要判断下一个节点是不是和上一个节点相同，相同的话就必须跳过。
代码如下：
代码语言：javascript复制public class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
solve(candidates, 0, target, new LinkedList<Integer>());
return ans;
}
private List<List<Integer>> ans=new LinkedList<>();
private void solve(int[] candidates,int start,int target,LinkedList<Integer> current){
if (target==0){
ans.add(copy(current));
return;
}
if (start>=candidates.length){
return;
}
if (target<candidates[start]){
return;
}
else {
for (int iterator=start;iterator<candidates.length;iterator ){
if (candidates[iterator]>target){
break;
}
//如果该节点和上一个节点值相同，那么它的所有组合必然包括在上一个节点的所有组合里，必须跳过
if (iterator>start&&candidates[iterator]==candidates[iterator-1]){
continue;
}
current.add(candidates[iterator]);
solve(candidates, iterator 1, target - candidates[iterator], current); //每使用过iterator，就要 1，使得每个数只用一次
current.pollLast();
}
return;
}
}
private LinkedList<Integer> copy(LinkedList<Integer> source){
LinkedList<Integer> dest=new LinkedList<>();
for (int i:source){
dest.add(i);
}
return dest;
}
}
