1、遞歸方法

原集合每一個數(shù)字只有兩種狀態(tài)浆西，要么存在，要么不存在顽腾，那么在構(gòu)造子集時就有選擇和不選擇兩種情況近零，所以可以構(gòu)造一棵二叉樹，左子樹表示選擇該層處理的節(jié)點抄肖，右子樹表示不選擇久信，最終的葉節(jié)點就是所有子集合，樹的結(jié)構(gòu)如下：

捕獲.JPG

遞歸方法：

class Solution {
public:
    /**
     * @param nums: A set of numbers
     * @return: A list of lists
     */
    vector<vector<int>> subsets(vector<int> &nums) {
        // write your code here
        vector<vector<int>> res;
        if(nums.size() == 0){
            res.push_back(nums);
            return res;
        }
        sort(nums.begin(),nums.end());
        vector<int> temp;
        help(res,nums,0,temp);
        return res;
    }
    
    void help(vector<vector<int>> &res, vector<int> &nums,int i,vector<int> p){
        if(i == nums.size()){//基本情況漓摩，添加結(jié)果裙士，退出
            res.push_back(p);
            return;
        }else{
            help(res,nums,i+1,p);//不加入當(dāng)前節(jié)點，處理后續(xù)節(jié)點
                                              //注意 p在當(dāng)前層的值不變
            p.push_back(nums[i]);//加入當(dāng)前節(jié)點
            help(res,nums,i+1,p);//處理后續(xù)節(jié)點
        }
    }
    
    
};

1管毙、非遞歸方法

思路分析：n個元素的子集共有2^n個腿椎，其中包括空集。
（1）假設(shè)有3個元素｛a, b, c｝夭咬，那么此時有 2^3 個子集啃炸，即8個子集。
（2）因為有8個子集卓舵，而且包括空集南用，注意7對應(yīng)的二進制形式為111，并且二進制數(shù)剛好3位；所以（000 ～ 111）可分別對應(yīng)一個子集裹虫，若該位為1肿嘲，則表示該元素出現(xiàn)在子集中，若該位為0恒界，則表示該元素不出現(xiàn)在子集中睦刃；
（3）注意：001中的1在低位，對應(yīng)的是a十酣，即數(shù)組中的首個元素涩拙。
（4）舉例
111表示子集abc；
110表示子集bc耸采；
101表示子集ac兴泥；
100表示子集c；
011表示子集ab
010表示子集b虾宇；
001表示子集a搓彻；
000則表示空集；

class Solution {
public:
    /**
    * @param nums: A set of numbers
    * @return: A list of lists
    */
    vector<vector<int>> subsets(vector<int> &nums) {
        // write your code here
        int len = nums.size();
        vector<vector<int>> res;
        if (len == 0) {
            res.push_back(nums);
            return res;
        }

        int n = 1 << len;//一共有多少個子集

        for (int i = 0; i < n; i++) {
            vector<int> line;
            int mark = i;//當(dāng)循環(huán)內(nèi)部對i處理時 必須處理i的備份
            int j = 0;//遍歷當(dāng)前i值
            while (mark > 0) {
                if (mark & 1) {
                    line.push_back(nums[j]);
                }
                mark = mark >> 1;
                j++;
            }
            res.push_back(line);//保存當(dāng)前i的子集
        }

        return res;
    }
};