今日题目、
给定一个数组 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 <= 100 1 <= candidates[i] <= 50 1 <= target <= 30
思路
这道题相较于组合总和1的区别是：
- 1、每个元素不能再无限使用，而是只能用一次，因此每次递归的下标不能再从当前小标开始，而是i+1开始。
- 2、元素有重复元素，因此需要去重。
上述两点都有去重的效果，一个是在结果上保证了没有重复元素，一个是保证在横向遍历的时候保证没有重复搜索。 除此之外与大多数回溯思路一样。
递归遍历数组，每次首先判断当前下标元素是否与前一个元素相同，如果相同同时判断上一个元素是否正在使用，如果没有使用则直接跳过，因为上一个元素前面已经遍历过了。
然后判断当前元素是否小于等于target，如果大于target，则说明如果target减去当前元素差一定小于0，不满足等于0，直接break循环就可以了。因为该元素之后的元素一定是大于等于当前元素的，因此target减去该元素的差也一定是小于0的，所以直接跳过。这是一步非常重要的剪枝操作。
将当前元素加入path列表，将当前vis[i]设置为true表示已访问。
进入递归，判断target是否为0，如果为0，加入答案列表。
出递归，需要进行回溯，将当前元素从path列表中删除，并将访问置为false。
总结成两个问题：
- 1.如何保证每个数字在每个组合中只使用一次？ 答：每次递归调用方法时，从当前数的下一个数开始
- 2.如何保证解集不能包含重复的组合？ 答：在有序数组中，如果索引i处的数字 等于 索引i-1处的数字，就直接跳过i，进入下一轮循环
还是使用如下框架代码：
result = [] backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择
代码实现：
List<List<Integer>> result = new LinkedList<>(); public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<Integer> list = new ArrayList<>(); Arrays.sort(candidates); combinationList(candidates, 0, target, list); return result; } public void combinationList(int[] candidates, int start, int target, List<Integer> list{ if (target == 0) { result.add(new ArrayList<>(list)); return; } for (int i = start; i < candidates.length; i++) { // 剪裁情况一 if (target - candidates[i] < 0) { break; } // 剪裁情况二 if (i > start && candidates[i] == candidates[i - 1]) { continue; } list.add(candidates[i]); // 此处为i+1,因为元素不可重复使用，当用start+1时,会导致重复计算 combinationList(candidates, i + 1, target - candidates[i], list); // 回溯 list.removeLast(); } }
执行用时：2 ms, 在所有 Java 提交中击败了99.32%的用户
内存消耗：38.4 MB, 在所有 Java 提交中击败了85.81%的用户
小结
回溯算法解题整体都是有着类似的目的，都是在寻找所有可行解的题，我们都可以尝试用搜索回溯的方法来解决。同时要记住算法实现的基本框架，可以大大减少实现难度。
