博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
图 - 深度优先遍历,回溯:leetcode 39,
阅读量:5100 次
发布时间:2019-06-13

本文共 1057 字,大约阅读时间需要 3 分钟。

深度优先遍历:

从0开始,到1,发现1只和0连接,退回到1,接着到2,再退回到1,接着到5,5和3有连接,再到3,3和4有连接,再到4,4和6有连接,再到6。最后6的相邻结点被遍历完,退回到4,3,5,0,结束。

应用:求连通分量

回溯法+深搜:

注意一定要先将candidates从小到大排序。

class Solution {public:    vector
> combinationSum(vector
& candidates, int target) { vector
> results{}; vector
result{}; sort(candidates.begin(), candidates.end()); dfs(results, result, candidates, target, 0); return results; } void dfs(vector
>& results, vector
& result, vector
& candidates, int target, int level){ if(target==0){ results.push_back(result); return; } //find for(int i=level; i
=0 ; ++i){ result.push_back(candidates[i]); dfs(results, result, candidates, target-candidates[i], i); result.pop_back(); } }};

 

转载于:https://www.cnblogs.com/Bella2017/p/10771373.html

你可能感兴趣的文章
基于node/mongo的App Docker化测试环境搭建
查看>>
java web 中base64传输的坑
查看>>
java 中的线程(一)
查看>>
秒杀9种排序算法(JavaScript版)
查看>>
素数判断BFS之“Prime Path”
查看>>
Activiti入门 -- 环境搭建和核心API简介
查看>>
struts.convention.classes.reload配置为true,tomcat启动报错
查看>>
MySQL的并行复制多线程复制MTS(Multi-Threaded Slaves)
查看>>
Django中间件
查看>>
xcode 5.1安装vvdocument
查看>>
好玩的-记最近玩的几个经典ipad ios游戏
查看>>
MySQL更改默认的数据文档存储目录
查看>>
替代微软IIS强大的HTTP网站服务器工具
查看>>
6.5 案例21:将本地数据库中数据提交到服务器端
查看>>
PyQt5--EventSender
查看>>
android 通过AlarmManager实现守护进程
查看>>
Sql Server 中由数字转换为指定长度的字符串
查看>>
win7下把电脑设置成wlan热
查看>>
Java 多态 虚方法
查看>>
jquery.validate插件在booststarp中的运用
查看>>