https://leetcode.cn/problems/combination-sum-ii/description/

解法一（java）：

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

    public void backStrack(int index,List<List<Integer>> result,List<Integer> tmp,int[] candidates,int target) {
        if (target == 0) {
            result.add(new ArrayList<>(tmp));
            return;
        }
        if (target < 0) {
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            if (i > index && candidates[i-1] == candidates[i]) {
                continue;
            }
            tmp.add(candidates[i]);
            backStrack(i + 1,result,tmp,candidates,target - candidates[i]);
            tmp.remove(tmp.size()-1);
        }
    }

}

思路：回溯法，参考http://www.haijin.xyz/article/566

if (i > start && candidates[i] == candidates[i-1]) {
    continue;
}

为什么需要跳过重复元素？
假设输入数组为 [1,1,2,5]，目标为 8，如果不跳过重复元素，可能会得到：

[1,2,5] (第一个1)

[1,2,5] (第二个1)
这两个组合实际上是相同的，只是选择了不同位置的1。

i > start 条件：

确保我们不是在该层的第一个元素（允许第一个重复元素被选择）

start 表示当前递归层级开始选择的起始位置

candidates[i] == candidates[i-1]：

检查当前元素是否与前一个元素相同

continue：

如果上述条件满足，则跳过当前元素

排序数组：首先对候选数组进行排序，这是为了后续能够方便地跳过重复元素

• 终止条件：

  • 当 target == 0 时，说明当前组合的和正好等于目标值，将组合加入结果集

  • 当 target < 0 时，说明当前组合的和已经超过目标值，直接返回

• 递归过程：

  • 从给定的 index 开始遍历候选数组

  • 跳过重复元素：当发现当前元素与前一个元素相同且不是该层的第一个元素时，跳过以避免重复组合

  • 选择当前元素：将当前元素加入临时组合，然后递归处理剩余的目标值

  • 撤销选择：回溯时移除最后加入的元素，尝试其他可能性