当前位置：首页 > article >正文

LeetCode40：组合总和II

article 2024/11/14 22:45:08

原题地址：. - 力扣（LeetCode）

题目描述

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

解题思路

从给定的候选数字数组 candidates 中找出所有和为 target 的组合，但与之前的问题不同，这个变种允许使用候选数字数组中的数字多次，且组合中的数字不一定要连续。代码中使用了深度优先搜索（DFS）算法来解决这个问题，并进行了一些优化：

预处理：首先对候选数字数组进行排序，并使用 freq 数组来存储每个不同数字的频率。
DFS：深度优先搜索函数 dfs 用于递归地构建所有可能的组合。

在 dfs 方法中，我们有两个选择：

跳过当前数字：直接递归调用 dfs 方法，尝试下一个数字。
选择当前数字：如果当前目标 rest 大于等于候选数字，则将该数字添加到 sequence 列表中，并递归调用 dfs 方法，目标减去该数字的倍数，直到超过剩余目标或超过当前数字的频率。

代码实现

class Solution {
    // 存储每个数字的频率
    List<int[]> freq = new ArrayList<>();
    // 存储所有有效的组合
    List<List<Integer>> ans = new ArrayList<>();
    // 存储当前的组合
    List<Integer> sequence = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 对候选数字数组进行排序
        Arrays.sort(candidates);
        // 计算每个数字的频率
        for (int num : candidates) {
            int size = freq.size();
            // 如果当前数字与前一个数字不同，或者freq为空，则添加新的频率记录
            if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
                freq.add(new int[]{num, 1});
            } else {
                // 否则，增加相同数字的频率
                ++freq.get(size - 1)[1];
            }
        }
        // 开始深度优先搜索
        dfs(0, target);
        // 返回所有有效的组合
        return ans;
    }

    public void dfs(int pos, int rest) {
        // 如果剩余目标为0，说明找到了一个有效的组合，添加到结果列表中
        if (rest == 0) {
            ans.add(new ArrayList<>(sequence));
            return;
        }
        // 如果位置超出freq数组范围，或者剩余目标小于当前数字，返回
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            return;
        }

        // 先不选择当前数字，递归搜索下一个数字
        dfs(pos + 1, rest);

        // 选择当前数字，最多选择至多等于剩余目标或当前数字频率的最小值
        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i = 1; i <= most; ++i) {
            // 将当前数字添加到组合中
            sequence.add(freq.get(pos)[0]);
            // 递归搜索下一个数字，目标减去当前数字
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        // 回溯，移除添加的当前数字
        for (int i = 1; i <= most; ++i) {
            sequence.remove(sequence.size() - 1);
        }
    }
}

复杂度分析

时间复杂度：最坏情况下，DFS 会尝试所有可能的组合，但由于进行了剪枝（即跳过大于剩余目标的数字），实际的时间复杂度通常要好于 O(2^n)，但最坏情况下仍然是指数级别的。

空间复杂度：空间复杂度主要取决于递归栈的深度和 sequence 列表的大小。最坏情况下，递归栈的深度和 sequence 的大小都不超过 target，所以空间复杂度为 O(target)。

查看全文

http://www.kler.cn/a/393576.html