leetcode 求subset的这个递归解法是什么意思

版里 戴方勤 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通过,尽管效率差些
求指教!!!

建议专门选几个类似的问题在leetcode或者lintcode上集中解决，体会体会其中的相似之处。

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

看在我真诚分享的份上，给我加点大米吧！lol

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

以上思路参考：https://segmentfault.com/a/1190000003498803

lz可以想一下递归搜索树，这段代码里面的private method是帮助你沿着其中一条路径 DFS走下去，并且把路上路过的 node (值）都加入path中。每次path return了就代表这条path探索完了，需要做一个 back track，往回走一步，然后去看其他的路径，直到搜索完所有路径为止。其中 path.push这里是加目前的node，然后递归调用往下走 （step + 1 )，而return之后的 path.pop则是back track，去探索其他的path

mnmunknown 发表于 2015-2-16 08:32
lz可以想一下递归搜索树，这段代码里面的private method是帮助你沿着其中一条路径 DFS走下去，并且把路上路 ...

怎样把{1, 2, 3}的subset想象成递归树?

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

mnmunknown 发表于 2015-2-16 11:54
想开始你的path是空的。

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

是唉, 大谢!

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

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

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

hanrui_542 发表于 2015-2-16 12:12
是唉, 大谢!

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

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

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

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

hanrui_542 发表于 2015-2-16 12:12
是唉, 大谢!

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

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

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