[leetcode] Subsets


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();
    }
};

 

 

Untitled

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.