网站 板块 栏目,学设计在哪学,抖音开放平台官网入口,手机网站建设原则原题地址#xff1a;. - 力扣#xff08;LeetCode#xff09; 题目描述 给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意#xff… 原题地址. - 力扣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 1001 candidates[i] 501 target 30 解题思路 从给定的候选数字数组 candidates 中找出所有和为 target 的组合但与之前的问题不同这个变种允许使用候选数字数组中的数字多次且组合中的数字不一定要连续。代码中使用了深度优先搜索DFS算法来解决这个问题并进行了一些优化 预处理首先对候选数字数组进行排序并使用 freq 数组来存储每个不同数字的频率。DFS深度优先搜索函数 dfs 用于递归地构建所有可能的组合。 在 dfs 方法中我们有两个选择 跳过当前数字直接递归调用 dfs 方法尝试下一个数字。选择当前数字如果当前目标 rest 大于等于候选数字则将该数字添加到 sequence 列表中并递归调用 dfs 方法目标减去该数字的倍数直到超过剩余目标或超过当前数字的频率。 代码实现
class Solution {// 存储每个数字的频率Listint[] freq new ArrayList();// 存储所有有效的组合ListListInteger ans new ArrayList();// 存储当前的组合ListInteger sequence new ArrayList();public ListListInteger 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)。
