leet code 40. 组合总和 II

40. 组合总和 II

题目描述

给定一个候选人编号的集合 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

题目解析

• 明确题目要求
• 从一个函数重复元素的数组中，选取所有不重复的组合，使其和等于 target
• 以数组 [1, 2, 2, 2, 5] 为例，选取和为 5 的组合
• 现在我们开始选取元素

• 选择 idx = 0 --> [1]
• 选择 idx = 1 --> [1, 2]
• 选择 idx = 2 --> [1, 2, 2] 符合要求，添加到结果集中
• 新一轮选择
• 选择 idx = 0 --> [1]
• 选择 idx = 1 --> [1, 2]
• 选择 idx = 2, val = 2 重复元素，跳过
• 选择 idx = 3, val = 2 重复元素，跳过
• 选择 idx = 4, --> [1, 2, 5] 不符合要求

• 所以，我们要考虑如何在代码中去除重复元素的情况

• 也就是，重复元素的取值方案仅执行1次
• 如下代码

for(int i = 0;i < ...;i++) {
    if(i > 0 && xxx[i] == xxx[i - 1]) {
        continue;
    }
}

show code

class Solution {
    private List<List<Integer>> ans;

    private int[] candidates;

    private int target;

    // 追踪路径上的和.
    private int trackSum;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 初始化结果集合
        ans = new ArrayList<>();
        // 赋值全局变量
        this.candidates = candidates;
        this.target = target;

        // 数组排序
        Arrays.sort(candidates);

        //  0     : 表示遍历到的当前元素的数组索引下标
        //  local : 表示把路径上的元素添加到  local 中
        List<Integer> local = new ArrayList<>();
        dfs(0, local);

        return ans;
    }

    private void dfs(int idx, List<Integer> local) {
        if(target == trackSum) {
            // 符合要求，添加到结果集合中
            ans.add(new ArrayList<>(local));
            return;
        }
        if(target < trackSum) {
            // 大于目标值，直接返回
            return;
        }
        for(int i = idx;i < candidates.length;i++) {
            // 值相同的树枝，只遍历一条
            if(i > idx && candidates[i] == candidates[i - 1]) {
                continue;
            }
            local.add(candidates[i]);
            trackSum += candidates[i];

            dfs(i + 1, local);

            local.remove(local.size() - 1);
            trackSum -= candidates[i];
        }
    }
}