一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1760|回复: 9
收起左侧

[算法题] leetcode 求subset的这个递归解法是什么意思

[复制链接] |试试Instant~ |关注本帖
hanrui_542 发表于 2015-2-16 07:29:13 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 hanrui_542 于 2015-2-16 07:36 编辑

版里 戴方勤 leetcode题解里对求给定 set 的所有subset这题给了这么一个解法:
  1. // LeetCode, Subsets
  2. // 增量构造法,深搜,时间复杂度 O(2^n),空间复杂度 O(n)
  3. class Solution {
  4. public:
  5.     vector<vector<int> > subsets(vector<int> &S) {
  6.     sort(S.begin(), S.end()); // 输出要求有序
  7.     vector<vector<int> > result;
  8.     vector<int> path;
  9.     subsets(S, path, 0, result);
  10.     return result;
  11. }
  12. private:
  13.     static void subsets(const vector<int> &S, vector<int> &path, int step, vector<vector<int> > &result) {
  14. if (step == S.size()) {
  15. result.push_back(path);
  16. return;
  17. }
  18. // 不选 S[step]
  19. subsets(S, path, step + 1, result);
  20. // 选 S[step]
  21. path.push_back(S[step]);
  22. subsets(S, path, step + 1, result);
  23. path.pop_back();
  24. }
复制代码
这个解法怎么理解,这个怎么想出来的?想了半天不知道几个意思.oj通过,尽管效率差些
求指教!!!
mnmunknown 发表于 2015-2-16 12:50:37 | 显示全部楼层
建议专门选几个类似的问题在leetcode或者lintcode上集中解决,体会体会其中的相似之处。

比如此类 DFS题有 subsets, permutation, 然后是有重复元素的 subsets, permutation, N queens,等等。。。其实都可以用同一个递归思路解决,只是细节上略有不同。我当初花了大概整整2~3天反复啃这几道题,理解的比较透彻之后就好了。

看在我真诚分享的份上,给我加点大米吧!lol
回复 支持 1 反对 0

使用道具 举报

mnmunknown 发表于 2015-2-16 08:32:44 | 显示全部楼层
lz可以想一下递归搜索树,这段代码里面的private method是帮助你沿着其中一条路径 DFS走下去,并且把路上路过的 node (值)都加入path中。每次path return了就代表这条path探索完了,需要做一个 back track,往回走一步,然后去看其他的路径,直到搜索完所有路径为止。其中 path.push这里是加目前的node,然后递归调用往下走 (step + 1 ),而return之后的 path.pop则是back track,去探索其他的path
回复 支持 反对

使用道具 举报

 楼主| hanrui_542 发表于 2015-2-16 11:41:48 | 显示全部楼层
mnmunknown 发表于 2015-2-16 08:32
lz可以想一下递归搜索树,这段代码里面的private method是帮助你沿着其中一条路径 DFS走下去,并且把路上路 ...

怎样把{1, 2, 3}的subset想象成递归树?
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2015-2-16 11:54:12 | 显示全部楼层
hanrui_542 发表于 2015-2-16 11:41
怎样把{1, 2, 3}的subset想象成递归树?

想开始你的path是空的。

第一步的时候加进去了 {1},然后调用了自身去看下一个。

这次调用是带着上次的结果{1}来的,所以一开始把这个加到了result里面作为一个subset. 然后他加了个新元素,path变成了{1, 2},以此类推到走到底为止。

这时候想一下 {1, 2} 的那个函数已经return了,这时候它会把自己的最后一个元素删掉,重新变成{1},然后去探索其他元素的可能性,这个删掉的步骤就是back track,而这条path会继续找,找到比如{1, 3} 这种。

从一开始的{1}的角度看, return之后会删掉最后这个{1},back track之后去找其他的,顺着这个路线继续找它会发现{2}开始的新path
回复 支持 反对

使用道具 举报

 楼主| hanrui_542 发表于 2015-2-16 12:12:56 | 显示全部楼层
本帖最后由 hanrui_542 于 2015-2-16 12:17 编辑
mnmunknown 发表于 2015-2-16 11:54
想开始你的path是空的。

第一步的时候加进去了 {1},然后调用了自身去看下一个。

是唉, 大谢!

我想攻克用深搜的一类面试题, 请问有什么参考资料对dfs讲的比较透彻? 我对dfs的理解只局限于CLRS里对给定图的搜索.  对leetcode里的一类题很头疼. 谢谢!!

回复 支持 反对

使用道具 举报

DWill008 发表于 2015-2-17 07:27:16 | 显示全部楼层
http://blog.csdn.net/u011095253/article/details/9158387

楼主去把这个贴子里面的题目按照列出的顺序做一下吧,做完之后我感觉DFS问题应该就差不多了。
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2015-2-17 13:59:16 | 显示全部楼层
hanrui_542 发表于 2015-2-16 12:12
是唉, 大谢!

我想攻克用深搜的一类面试题, 请问有什么参考资料对dfs讲的比较透彻? 我对dfs的理解只局 ...

建议你集中做一个同类题,理解就上去了,因为思路和结构都一样,只是细节上略有差别。

subsets, subsets II (有重复元素),permutation, permutation II (有重复元素),N-Queens (变种的permutation)

类型题多做,多总结多比较就好了~ 求大米!

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

DWill008 发表于 2015-2-17 13:59:43 | 显示全部楼层
hanrui_542 发表于 2015-2-16 12:12
是唉, 大谢!

我想攻克用深搜的一类面试题, 请问有什么参考资料对dfs讲的比较透彻? 我对dfs的理解只局 ...

http://blog.csdn.net/u011095253/article/details/9158387

lz有兴趣的话可以去看看这个贴子,作者把leetcode上面用dfs做的题目整理了一遍。我感觉把这个做完就应该就差不多了...

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

芥末青豆 发表于 2016-11-15 11:36:27 | 显示全部楼层
按照楼主给的解法,我理解这并不是backtracking的经典解法,因为代码中并没有trace back 的过程。 反观这个解法,我认为可以理解成一个二叉树,二叉树的根是个空集,它的左子节点是加上第一个元素产生的集合,右子节点不加上第一个元素所产生的集合。以此类推,左子节点的左子节点是加上第二个元素,左子节点的右子节点是不加上第二个元素。而解就是这个二叉树所有的路径,我们要做的就是根据加,或者不加下一元素,来产生一个新的集合,然后继续递归直到终点。另外需要先排序以满足题目要求。

以上思路参考:https://segmentfault.com/a/1190000003498803
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 12:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表