题意
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
题解
该题和39的区别是，1.数字有重复的 2.每个数字不能重复使用 3.不能包含重复的组合。算法：回溯+剪枝
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> ress = new ArrayList<>();
Arrays.sort(candidates);
combImpl(candidates, 0, target, ress, new Stack<Integer>());
return ress;
}
private void combImpl(int[] cadidates, int pos, int target, List<List<Integer>> ress, Stack<Integer> st) {
if (target == 0) {
ress.add(new ArrayList<>(st));
return;
}
for (int i = pos; i < cadidates.length && (target - cadidates[i] >= 0); i++) {
// 判断当前值和前一个值相等，则跳过，不然计算出来的组合和前面的一致
if (i > pos && cadidates[i] == cadidates[i-1]) {
continue;
}
st.push(cadidates[i]);
// 注意这里和39题的区别，由于数字不能重复获取，所以这个pos位置要取后一个位置
combImpl(cadidates, i+1, target-cadidates[i], ress, st);
st.pop();
}
}
}
