【算法刷题】—7.19深度优先搜索,回溯解决实际问题

简介: ✨今日算法一题组合总和

✨今日算法一题



由于最近事情变多,每日刷题暂时调整为一题,刷题不一定贪多,但是要刷一题有用一题。


组合总和


文章目录


组合总和


题目描述

思路详解


本题相对比较难,下面是参考官方解答的自我解释。方法:回溯。

首先我们定义三个成员变量这样递归的时候就不用每次都传入了。


  • 我们用dfs(pos,rest) 表示递归的函数,其中pos 表示我们当前递归到了数组 candidates 中的第 \textit{pos}pos 个数,而rest 表示我们还需要选择和为rest 的数放入列表作为一个组合;
  • 对于当前的第 pos 个数,我们有两种方法:选或者不选。如果我们选了这个数,那么我们调用dfs(pos+1,rest−candidates[pos]) 进行递归,注意这里必须满足 rest≥candidates[pos]。如果我们不选这个数,那么我们调用 dfs(pos+1,rest) 进行递归;
  • 在某次递归开始前,如果rest 的值为 0,说明我们找到了一个和为 target 的组合,将其放入答案中。每次调用递归函数前,如果我们选了那个数,就需要将其放入列表的末尾,该列表中存储了我们选的所有数。在回溯时,如果我们选了那个数,就要将其从列表的末尾删除。

为了解决重复的问题,这里采用哈希映射(HashMap)


  • 我们使用一个哈希映射(HashMap)统计数组 candidates 中每个数出现的次数。在统计完成之后,我们将结果放入一个列表 \freq 中,方便后续的递归使用。
  • 列表 freq 的长度即为数组 candidates 中不同数的个数。其中的每一项对应着哈希映射中的一个键值对,即某个数以及它出现的次数。
  • 在递归时,对于当前的第pos 个数,它的值为 freq[pos][0],出现的次数为 freq[pos][1],那么我们可以调用dfs(pos+1,rest−i×freq[pos][0])
  • 即我们选择了这个数 i 次。这里 i 不能大于这个数出现的次数,并且 i×freq[pos][0] 也不能大于 rest。同时,我们需要将 i 个 freq[pos][0] 放入列表中。


代码与结果

class Solution {
    List<int[]> freq = new ArrayList<int[]>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> sequence = new ArrayList<Integer>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        for (int num : candidates) {
            int size = freq.size();
            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) {
        if (rest == 0) {
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        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);
        }
    }
}


✨总结


深度优先算法比较难懂,也比较重要更加多加练习!



相关文章
|
5月前
|
算法 测试技术 定位技术
数据结构与算法——DFS(深度优先搜索)
数据结构与算法——DFS(深度优先搜索)
|
22天前
|
运维 监控 JavaScript
内网网管软件中基于 Node.js 的深度优先搜索算法剖析
内网网管软件在企业网络中不可或缺,涵盖设备管理、流量监控和安全防护。本文基于Node.js实现深度优先搜索(DFS)算法,解析其在网络拓扑遍历中的应用。通过DFS,可高效获取内网设备连接关系,助力故障排查与网络规划。代码示例展示了图结构的构建及DFS的具体实现,为内网管理提供技术支持。
39 11
|
22天前
|
机器学习/深度学习 算法
算法系列之搜索算法-深度优先搜索DFS
深度优先搜索和广度优先搜索一样,都是对图进行搜索的算法,目的也都是从起点开始搜索,直到到达顶点。深度优先搜索会沿着一条路径不断的往下搜索,直到不能够在继续为止,然后在折返,开始搜索下一条候补路径。
97 62
算法系列之搜索算法-深度优先搜索DFS
|
5天前
|
算法 安全 Java
算法系列之深度优先搜索寻找妖怪和尚过河问题的所有方式
在算法学习中,深度优先搜索(DFS)是一种常用的图搜索算法,通过递归或栈实现,适合路径搜索、连通性、拓扑排序、回溯、生成、环路检测、强连通分量和可达性等问题。本文将介绍如何利用深度优先搜索解决“妖怪和尚过河问题”的所有方式。
54 26
算法系列之深度优先搜索寻找妖怪和尚过河问题的所有方式
|
16天前
|
算法 Java
算法系列之回溯算法
回溯算法(Backtracking Algorithm)是一种通过穷举来解决问题的方法,它的核心思想是从一个初始状态出发,暴力搜索所有可能的解决方案,遇到正确解将其记录,直到找到了所有的解或者尝试了所有的可能为止。
31 4
算法系列之回溯算法
|
23天前
|
存储 人工智能 算法
【深度优先搜索篇】走迷宫的魔法:算法如何破解迷宫的神秘密码
【深度优先搜索篇】走迷宫的魔法:算法如何破解迷宫的神秘密码
|
4月前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
170 23
|
4月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
4月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
4月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明

热门文章

最新文章