Leetcode---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，其中关键在于空集合的处理，空集合什么时候产生？？

vector<vector<int> > f(vector<int> &S, int index){
    vector<vector<int> > result;
    vector<int> tmp;
    int n=S.size()-index;
    if(n==0)
        return result;
    if(n==1){
        result.push_back(tmp);
        tmp.push_back(S[index]);
        result.push_back(tmp);
        return result;
    }
    vector<vector<int> > _result=f(S,index+1);
    for(int i=0;i<_result.size();i++){
        tmp.clear();
        result.push_back(_result[i]);
        tmp.push_back(S[index]);
        tmp.insert(tmp.begin()+1,_result[i].begin(),_result[i].end());
        result.push_back(tmp);
    }
    return result;
}
vector<vector<int> > subsets(vector<int> &S) {
    sort(S.begin(),S.end());
    return f(S,0);
}

vector<vector<int> > subsets(vector<int>& S) {
    vector<vector<int> > result;
    if(S.size()==0){
        result.push_back(S);
    }
    while(S.size()>0){
        int last=S.back();
        S.pop_back();
        vector<int> s(S);
        vector<vector<int> > temp=subsets(s);
        for(int i=0;i<temp.size();i++){
            temp[i].push_back(last);
            result.push_back(temp[i]);
        }
        if(temp.size()==1){
            vector<int> a;
            result.push_back(a);
        }
    }
    return result;
}

Leetcode---Subsets

原文：http://blog.csdn.net/ffmpeg4976/article/details/44904033