lintcode 17 子集

1、递归方法

原集合每一个数字只有两种状态，要么存在，要么不存在，那么在构造子集时就有选择和不选择两种情况，所以可以构造一棵二叉树，左子树表示选择该层处理的节点，右子树表示不选择，最终的叶节点就是所有子集合，树的结构如下：

捕获.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()){//基本情况，添加结果，退出
            res.push_back(p);
            return;
        }else{
            help(res,nums,i+1,p);//不加入当前节点，处理后续节点
                                              //注意 p在当前层的值不变
            p.push_back(nums[i]);//加入当前节点
            help(res,nums,i+1,p);//处理后续节点
        }
    }
    
    
};

1、非递归方法

思路分析：n个元素的子集共有2^n个，其中包括空集。
（1）假设有3个元素｛a, b, c｝，那么此时有 2^3 个子集，即8个子集。
（2）因为有8个子集，而且包括空集，注意7对应的二进制形式为111，并且二进制数刚好3位；所以（000 ～ 111）可分别对应一个子集，若该位为1，则表示该元素出现在子集中，若该位为0，则表示该元素不出现在子集中；
（3）注意：001中的1在低位，对应的是a，即数组中的首个元素。
（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;//当循环内部对i处理时 必须处理i的备份
            int j = 0;//遍历当前i值
            while (mark > 0) {
                if (mark & 1) {
                    line.push_back(nums[j]);
                }
                mark = mark >> 1;
                j++;
            }
            res.push_back(line);//保存当前i的子集
        }

        return res;
    }
};