组合总和2 - 中等 - 算法题 - 算法 - 计算机

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。

示例 1:

示例 2:

题解一

	public List<List<Integer>> combinationSum2(int[] candidates, int target) {
	// 排序
	Arrays.sort(candidates);
	List<List<Integer>> result = new ArrayList<>();
	recursion(candidates, target, new ArrayList<>(), result, 0);
	return result;
	}

	public void recursion(int[] candidates, int target, List<Integer> list, List<List<Integer>> result, int start){
	// 去重
	if (target == 0 && !result.contains(list)){
	result.add(new ArrayList<>(list));
	return;
	}
	for (int i = start; i < candidates.length; i++){
	if (candidates[i] > target){
	return;
	}

	list.add(candidates[i]);
	recursion(candidates, target - candidates[i], list, result, i + 1);
	Integer remove = list.remove(list.size() - 1);
	// 如果删除的值与前一个相同，结束当前循环
	if (list.size() > 0 && remove.equals(list.get(list.size() - 1))) return;
	}
	}

题解二

	public List<List<Integer>> combinationSum2(int[] candidates, int target) {
	// 排序
	Arrays.sort(candidates);
	List<List<Integer>> result = new ArrayList<>();
	recursion(candidates, target, new ArrayList<>(), result, 0);
	return result;
	}
	public void recursion(int[] candidates, int target, List<Integer> list, List<List<Integer>> result, int start){
	if (target == 0){
	result.add(new ArrayList<>(list));
	return;
	}
	for (int i = start; i < candidates.length; i++){
	// 去重，本轮选择元素不能重复
	// 换句话解释：保证每次向下层递归时，当前层的组合是唯一的，这样能保证结果唯一
	if (i > start && candidates[i] == candidates[i - 1]) continue;

	if (candidates[i] > target){
	return;
	}

	list.add(candidates[i]);
	recursion1(candidates, target - candidates[i], list, result, i + 1);
	list.remove(list.size() - 1);
	}
	}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii