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], [] ] http://leetcode.com/onlinejudge#question_78

leetcode_subsets.cpp

void dfs(vector<int>& S, vector<vector<int> >& ret, vector<int>& cur, int kth) {
    if (kth == S.size()) {
        ret.push_back(cur);
        return;
    }
    dfs(S, ret, cur, kth + 1);
    cur.push_back(S[kth]);
    dfs(S, ret, cur, kth + 1);
    cur.pop_back();
}

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        sort(S.begin(), S.end());
        vector<vector<int> > ret;
        vector<int> cur;
        dfs(S, ret, cur, 0);
        return ret;
    }
};