组合总和 II-java

题目描述:
- 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
  
  candidates 中的每个数字在每个组合中只能使用一次。
  
  注意：解集不能包含重复的组合。
解题思想:
- 回溯法 + 剪枝 :
- 在给定的候选数数组中，通过递归搜索所有可能的组合，每次选择一个候选数，并尝试加入当前组合中。然后，更新目标值为原目标值减去当前候选数，并继续在剩余的候选数中递归搜索。当目标值减到0时，说明找到了一个符合条件的组合，将其加入结果列表中。如果目标值小于0，或者已经遍历完所有的候选数，即搜索到了叶子节点，则回溯到上一层，尝试其他的候选数。通过这种方式，不断地探索搜索空间，直到找到所有符合条件的组合为止。
  
  这种方法的关键在于通过递归和回溯来穷举所有可能的组合，同时利用排序和剪枝等技巧来减少搜索空间，提高效率
解题方法 :
1. 对候选数数组进行排序，这样可以方便后续处理重复的答案(结果)。

2. 然后，定义一个递归函数 des，该函数用于在当前位置 start 开始搜索符合条件的组合

- 在 des 函数中，首先进行终止条件的判断：

- 如果目标值 target 小于 0，或者 start 等于数组长度，说明已经越界，直接返回。

- 如果目标值 target 等于 0，说明找到了一个符合条件的组合，将其加入结果列表

- 中，并返回。

在递归的过程中，遍历候选数数组，从当前位置 start 开始：
- 如果当前元素和上一个元素相同，并且当前位置不是起始位置，跳过，避免重复组合。
- 否则，将当前元素加入到当前组合中，更新目标值为 target - candidates[i]，并将 start 更新为 i + 1，继续递归搜索。
- 搜索完成后，将当前元素从组合中移除，以便尝试其他组合。

以下是代码实现:

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target){
        Arrays.sort(candidates);
        List<List<Integer>> lists = new ArrayList<>();
        des(lists, new ArrayList<>(), candidates, target, 0);
        return lists;
    }

    private void des(List<List<Integer>> lists, List<Integer> list, int[] candidates, int target, int start) {
        if(target == 0) {
            lists.add(new ArrayList<>(list));
            return;
        }
        if(target < 0 || start == candidates.length) return;

        for (int i = start; i < candidates.length; i++) {
            if(i > start && candidates[i] == candidates[i - 1]) continue;
            list.add(candidates[i]);
            des(lists, list, candidates, target - candidates[i], i + 1);
            list.remove(list.size() - 1);
        }
    }
}