40. Combination Sum II

Backtracking

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> numList = new ArrayList<>();
        Arrays.sort(candidates); // 注意 candidates 中包含重复数字需要排除重复组合时则需要排序
        dfs(resultList, numList, 0, candidates, 0, target, false);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, List<Integer> numList, int sum, int[] candidates, int index, int target, boolean preChosen) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            resultList.add(new ArrayList<>(numList));
            return;
        }
        if (index == candidates.length) {
            // 注意该判断不能放在方法体开头，因为下方无论选与不选都推进了索引，那选择了最后一个满足条件的数字时我们需要收集结果，而不能因为推进了索引导致结果未被收集
            return;
        }

        // not choose
        dfs(resultList, numList, sum, candidates, index + 1, target, false);

        // 00
        // 01 对此重复的选择进行排除
        // 10
        // 11
        if (index > 0 && candidates[index] == candidates[index - 1] && preChosen == false) {
            return;
        }

        // choose
        numList.add(candidates[index]);
        dfs(resultList, numList, sum + candidates[index], candidates, index + 1, target, true);
        numList.remove(numList.size() - 1);
    }
}

Backtracking

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> numList = new ArrayList<>();
        Arrays.sort(candidates); // 注意 candidates 中包含重复数字需要排除重复组合时则需要排序
        dfs(resultList, numList, 0, candidates, 0, target);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, List<Integer> numList, int sum, int[] candidates, int startIndex, int target) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            resultList.add(new ArrayList<>(numList));
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            if (sum + candidates[i] > target) {
                // 剪枝优化
                break;
            }
            if (i > startIndex && candidates[i] == candidates[i - 1]) {
                // 同层去重
                continue;
            }
            numList.add(candidates[i]);
            dfs(resultList, numList, sum + candidates[i], candidates, i + 1, target);
            numList.remove(numList.size() - 1);
        }
    }
}

Reference

40. Combination Sum II