Subsets

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],
  []
]

深搜DFS。

每次选择压入该元素或是不压入该元素。注意re应该传引用。thisRe传引用或是copy都可以，但传引用可以减轻内存开销。

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        sort(S.begin(), S.end());
        vector<vector<int >> re;
        vector<int> thisRe;
        _subsets(S, 0, re, thisRe);
        return re;
    }
    void _subsets(vector<int> &s, int idx, vector<vector<int >>& re, vector<int>& thisRe){
        if(idx == s.size()){
            re.push_back(thisRe);
            return ;
        }
        _subsets(s, idx + 1, re, thisRe); // don't push s[idx]
        thisRe.push_back(s[idx]);
        _subsets(s, idx + 1, re, thisRe); //push s[idx]
        thisRe.pop_back();
    }
};