组合总和II（LeetCode 40）
一、题目描述
给定一个候选人编号的集合 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]
]
提示:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<Integer> path = new ArrayList<>();
// 先排序，方便把相同的元素集中到一起
Arrays.sort(candidates);
backtrack( candidates , target , path , 0 );
return res;
}
// 1、画出递归树，找到状态变量(回溯函数的参数)
// start 表示递归时正在访问的数组元素下标
// nums 表示当前集合中的元素
// target 表示想在当前区间拼凑出的目标值
// path 表示选择的路径
private void backtrack(int[] nums,int target,List<Integer> path,int start) {
// 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
if (target < 0) {
// 一些逻辑操作（可有可无，视情况而定）
// 比如，在 N 皇后问题中，在这一步把数据加入到了结果里面
return;
}
if(target == 0 ){
// 找到一个组合了
res.add(new ArrayList(path));
return;
}
// 3、确定选择列表，即需要把什么数据存储到结果里面
// for 循环就是一个选择的过程
// i 等于 start 表示，后续可以选的元素一开始只能从 start 开始
// 比如 nums = [2,3,6,7]
// i = 1，指向了元素 3 ，表示当前后续选择的过程中，只能从 3 开始选，可以重复选 3 ，但无法选 2 了
// i = 2，指向了元素 6 ，表示当前后续选择的过程中，只能从 6 开始选，可以重复选 6 ，但无法选 2、3 了
for (int i = start ; i < nums.length ; i++ ) {
// 剪枝操作：同一层相同数值的结点，从第 2 个开始，结果一定发生重复，因此跳过，用 continue
if( i > start && nums[i] == nums[i - 1]){
continue;
}
// 当前路径上可以把 nums[i] 加上
path.add(nums[i]);
// 一些逻辑操作（可有可无，视情况而定）
// 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
// 需要剪枝
// 此时，目标值 target，已经从 target 变成了 target - nums[i]
// 接下来需要去【某个区间中】拼凑 target - nums[i]
// 由于每个数字在每个组合中只能使用 一次
// 当前正在使用 nums[i]，那么为了拼凑 target - nums[i]，需要从使用 nums[i+1] 开始
// 而 i 前面的元素，比如 num[i]、 num[i-1]无法继续使用，实现了剪枝操作
int nowposition = i ;
// 5、做出选择，递归调用该函数，进入下一层继续搜索
// 递归
backtrack(nums, target - nums[i] , path , nowposition + 1 );
// 一些逻辑操作（可有可无，视情况而定）
// 6、撤销选择，回到上一层的状态
path.remove(path.size()-1);
}
}
}
2、C++ 代码
3、Python 代码
