【回溯算法】求目标和的组合方案(升级篇) ... |刷题打卡

简介: 【回溯算法】求目标和的组合方案(升级篇) ... |刷题打卡

题目描述



这是 LeetCode 上的40. 组合总和 II,难度为 Medium


给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。


candidates 中的每个数字在每个组合中只能使用一次。


说明:


  • 所有数字(包括目标数)都是正整数。
  • 解集不能包含重复的组合。


示例 1:


输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
复制代码


示例 2:


输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]
复制代码


DFS + 回溯解法



这道题和 39. 组合总和(中等) 几乎一样。


唯一的不同是这题每个数只能使用一次,而「39. 组合总和(中等)」中可以使用无限次。


我们再来回顾一下应该如何快速判断一道题是否应该使用 DFS + 回溯算法来爆搜。


这个判断方法,最早三叶在 37. 解数独(困难) 讲过。


总的来说,你可以从两个方面来考虑:


  • 1. 求的是所有的方案,而不是方案数。 由于求的是所有方案,不可能有什么特别的优化,我们只能进行枚举。这时候可能的解法有动态规划、记忆化搜索、DFS + 回溯算法。
  • 2. 通常数据范围不会太大,只有几十。 如果是动态规划或是记忆化搜索的题的话,由于它们的特点在于低重复/不重复枚举,所以一般数据范围可以出到 10510^510510710^7107,而 DFS + 回溯的话,通常会限制在 30 以内。


这道题数据范围是 30 以内,而且是求所有方案。因此我们使用 DFS + 回溯来求解。

我们可以接着 39. 组合总和(中等) 的思路来修改:


  1. 由于每个数字只能使用一次,我们可以直接在 DFS 中决策某个数是用还是不用。
  2. 由于不允许重复答案,可以使用 set 来保存所有合法方案,最终再转为 list 进行返回。当然我们需要先对 cs 进行排序,确保得到的合法方案中数值都是从小到大的。这样 set 才能起到去重的作用。对于 [1,2,1][1,1,2],set 不会认为是相同的数组。


class Solution {
    public List<List<Integer>> combinationSum2(int[] cs, int t) {
        Arrays.sort(cs);
        Set<List<Integer>> ans = new HashSet<>();
        List<Integer> cur = new ArrayList<>();
        dfs(cs, t, 0, ans, cur);
        return new ArrayList<>(ans);
    }
    /**
     * cs: 原数组,从该数组进行选数
     * t: 还剩多少值需要凑成。起始值为 target ,代表还没选择任何数;当 t = 0,代表选择的数凑成了 target
     * u: 当前决策到 cs[] 中的第几位
     * ans: 最终结果集
     * cur: 当前结果集
     */
    void dfs(int[] cs, int t, int u, Set<List<Integer>> ans, List<Integer> cur) {
        if (t == 0) {
            ans.add(new ArrayList<>(cur));
            return;
        }
        if (u == cs.length || t < 0) return;
        // 使用 cs[u]
        cur.add(cs[u]);
        dfs(cs, t - cs[u], u + 1, ans, cur);
        // 进行回溯
        cur.remove(cur.size() - 1);
        // 不使用 cs[u]
        dfs(cs, t, u + 1, ans, cur);
    }
}
复制代码


  • 时间复杂度: DFS 回溯算法通常是指数级别的复杂度(因此数据范围通常为 30 以内)。这里暂定 O(n∗2n)O(n * 2^n)O(n2n)
  • 空间复杂度:同上。复杂度为 O(n∗2n)O(n * 2^n)O(n2n)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.40 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
7天前
|
传感器 人工智能 监控
智慧电厂AI算法方案
智慧电厂AI算法方案通过深度学习和机器学习技术,实现设备故障预测、发电运行优化、安全监控和环保管理。方案涵盖平台层、展现层、应用层和基础层,具备精准诊断、智能优化、全方位监控等优势,助力电厂提升效率、降低成本、保障安全和环保合规。
智慧电厂AI算法方案
|
11天前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
39 4
|
21天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
7天前
|
传感器 人工智能 监控
智慧化工厂AI算法方案
智慧化工厂AI算法方案针对化工行业生产过程中的安全风险、效率瓶颈、环保压力和数据管理不足等问题,通过深度学习、大数据分析等技术,实现生产过程的实时监控与优化、设备故障预测与维护、安全预警与应急响应、环保监测与治理优化,全面提升工厂的智能化水平和管理效能。
智慧化工厂AI算法方案
|
19天前
|
机器学习/深度学习 人工智能 算法
青否数字人声音克隆算法升级,16个超真实直播声音模型免费送!
青否数字人的声音克隆算法全面升级,能够完美克隆真人的音调、语速、情感和呼吸。提供16种超真实的直播声音模型,支持3大AI直播类型和6大核心AIGC技术,60秒快速开播,助力商家轻松赚钱。AI讲品、互动和售卖功能强大,支持多平台直播,确保每场直播话术不重复,智能互动和真实感十足。新手小白也能轻松上手,有效规避违规风险。
|
21天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
21天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
21天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
21天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
21天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!