leetcode做题笔记|leetcode:Subsets 回溯|深搜|递归|leetcode

Given a set of distinct integers, S, return all possible subsets.
Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

题目地址： https://oj.leetcode.com/problems/subsets/ 解题思路：
这道题做了两种解法。
【leetcode做题笔记|leetcode:Subsets】解法1：
因为从S中每添加一个元素进来，下一层的集合=上一层的集合+每一个上一层的集合的后面加上新添加的那个元素。如下：
0----------[ ]
1----------[ ] [1]
2----------[ ] [1] [2] [1 2]
3----------[ ] [1] [2] [1 2] [3] [1 3] [2 3] [1 2 3]
.........
代码：

class Solution { public: vector > subsets(vector &S) { sort(S.begin(),S.end()); vector > ret(1); for(int i=0; i tmp=ret[j]; tmp.push_back(S[i]); ret.push_back(tmp); } } return ret; } };

解法2：用递归+回溯的方法，这个方法可能看代码会比较清晰。参考了别人的代码：

class Solution { public: vector > ret; vector > subsets(vector &S) { ret.clear(); sort(S.begin(),S.end()); vector tmpans; dfs(S,0,tmpans); return ret; } private: void dfs(vector &s,int loc,vector &tmp){ if(loc==s.size()){ ret.push_back(tmp); return; }tmp.push_back(s[loc]); dfs(s,loc+1,tmp); tmp.pop_back(); dfs(s,loc+1,tmp); } };