Lintcode(17) Subsets

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

Have you met this question in a real interview? 

Yes

Example

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

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

Note

Elements in a subset must be in non-descending order.

The solution set must not contain duplicate subsets.

这种subsets，combination什么的基本上是模板了，这个题目算是最基础的了，稍微麻烦点的就是在什么时候取最后结果， 或者是剪枝的时候动点手脚。 不过要从最基本理解就是画下树状图，想想就是明白了。 具体怎么写，参照backtracking的解法。 基本没啥好说的，除了空input需要输出一个空vector之外。。。

1:  class Solution {  
2:  public:  
3:    /**  
4:     * @param S: A set of numbers.  
5:     * @return: A list of lists. All valid subsets.  
6:     */  
7:    vector<vector<int> > subsets(vector<int> &nums) {  
8:         // write your code here  
9:      // template for backtracking  
10:      vector< vector<int> > res;  
11:      vector<int> solution;  
12:      sort(nums.begin(),nums.end());  
13:      dfs(res,solution, nums, 0);  
14:      return res;  
15:    }  
16:    void dfs(vector< vector<int> >& res, vector<int>& solution, vector<int> &nums, int index){  
17:      res.push_back(solution);  
18:      for (int i=index; i<nums.size(); i++){  
19:        solution.push_back(nums[i]);  
20:        dfs(res, solution, nums, i+1);  
21:        solution.pop_back();  
22:      }  
23:    }  
24:  };