（LeetCode 78）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.

题目要求 ：

求整数数组的所有子集

注意：

1、子集元素按非降序排列

2、不包含重复的子集

解题思路：

求解这类诸如子集的题目，都可以采用回溯法。（剪枝+递归）

代码如下：

class Solution {
private:
    vector<vector<int> > ans;
public:
    void collectSubSet(vector<int> &S,vector<int> x,int len,int idx){
        if(idx==len){
            vector<int> subset;
            for(int i=0;i<len;i++){
                if(x[i]!=0)
                    subset.push_back(S[i]);
            }
            sort(subset.begin(),subset.end(),less<int>());
            ans.push_back(subset);
            return;
        }
        x[idx]=0;
        collectSubSet(S,x,len,idx+1);
        x[idx]=1;
        collectSubSet(S,x,len,idx+1);
    }

    vector<vector<int> > subsets(vector<int> &S) {
        int len=S.size();
        vector<int> x(len);
 //       sort(S.begin(),S.end(),greater<int>());
        collectSubSet(S,x,len,0);
//        sort(ans.begin(),ans.end(),cmp());
        return ans;
    }
};