问题描述：

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

基本思路：

求子集问题可以转换为子集的二进制表示。

首先，一个包含n个元素的set，其子集个数为2^n; 可以对set中的元素按照二进制编号。每个子集可以表示为二进制形式。比如：[1,3]表示为二进制为101。所以，所有子集就是0～2^-1的二进制表示形式到子集的映射。

代码：

vector<vector<int> > subsets(vector<int> &S) {  //C++
        vector<vector<int> > result;
        int size = S.size();
        //add empty subset
        vector<int> tmp;
        result.push_back(tmp);
        
        int bound = 1<<size;
        for(int i = 1; i < bound; i++){
            vector<int> vec;
            int num = i;
            for(int j = size; j > 0 && num >0; j-- ){
                int tmp = (1 << j-1);
                if(num >= tmp){
                    vec.push_back(S[j-1]);
                    num -= tmp;
                }
            }
            sort(vec.begin(),vec.end());
            result.push_back(vec);
        }
        return result;
    }

[leetcode]Subsets