集合的所有子集(一)

C++ 解法, 执行用时: 0ms, 内存消耗: 8552KB, 提交时间: 2015-03-20

class Solution {
public:
    vector<vector<int>> re;
    vector<int> t;
    
    int subs(vector<int> &S,int depth,int maxD,int s)
    {
        if (depth == maxD)
        {
            re.push_back(t);
            return 0;
        }
        for (int i = s;i<S.size();i++)
        {
            t[depth] = S[i];
            subs(S,depth+1,maxD,i+1);
        }
        return 0;
    }
    vector<vector<int> > subsets(vector<int> &S) {
        re.clear();
        re.push_back(t);
        sort(S.begin(),S.end());
        for (int i = 0;i<S.size();i++)
        {
            t.resize(i+1);
            subs(S,0,i+1,0);
        }
        t.clear();
        return re;
    }
};

C++ 解法, 执行用时: 0ms, 内存消耗: 8552KB, 提交时间: 2015-03-20

#include<algorithm>

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int> > res;
        sort(S.begin(),S.end());
        int l = (1<<S.size()),i,j;
        for(i=0;i<l;i++){
            vector<int> x;
            for(j=0;j<32;j++){
                if(i&(1<<j)) x.push_back(S[j]);
            }
            res.push_back(x);
        }
        return res;
    }
};

C 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2020-12-04

/**
 * 
 * @param A int整型一维数组 
 * @param ALen int A数组长度
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
int caculcolumnSize(int n)
{                          //计算子集所需的空间，如n=6,二进制110，所需空间return 2
    int count=0;           //n=2 ,二进制010，所需空间return 1
    
    while(n>0)
    {
        if(((n>>1)<<1)==n)
        {
            n=n>>1;
            continue;
        }
        else
        {
            n=n>>1;
            count++;
        }
    }
    return count;
}

void fun(int *A,int *num,int i)
{
    int k=0;
    int count=0;
    while(i>0) 
    {
        if(((i>>1)<<1)==i)
        {
            i=i>>1;
        }
        else
        {
            i=i>>1;
            num[k++] = A[count];
        }
        count++;
    }
}
int** subsets(int* A, int ALen, int* returnSize, int** returnColumnSizes )
{
    // write code here
    //集合共有n个元素，它的子集的个数就是对这n个元素做组合，
    //共有n个位置可以组合，每个位置上该元素可以出现也可以不出现，所以最后总的个数为2的n次方。
    //利用二进制的思想 如 0110 1001，0表示该数组位置不选，1表示选中。
    int i = 0;
    int many = 0; //子集的个数
    
    many = (int)pow(2.0,ALen);  //计算所给集合的子集的个数
    int **num = (int**)malloc(sizeof(int*)*many);
    *returnColumnSizes=(int*)malloc(sizeof(int)*many);
    
    for(i=0; i<many; i++)
    {
        int columnSizes = caculcolumnSize(i);//子集大小
        num[i] = (int*)malloc(sizeof(int)*columnSizes);
        fun(A,num[i],i);
        (*returnColumnSizes)[i] = columnSizes;
    }
    *returnSize = many;
    return num;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 364KB, 提交时间: 2021-05-10

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int> > result;
        int size = S.size();
        if (size == 0)
            return result;
        
//         subset(result, 0, S, vector<int>());
//         sort(result.begin(), result.end());
        
        vector<int> sub;
        sort(S.begin(), S.end());
        result.push_back(sub);
        for (int i = 1; i <= S.size(); ++i) {
            subset(S, result, sub, 0, i);
        }
        return result;
    }
    
    // 方法1
//     void subset(vector<vector<int> > &vec, int index, vector<int> &S, vector<int> sub) {
//         if (index == S.size()) {
//             vec.push_back(sub);
//             return;
//         }
//         vector<int> no = sub;
//         subset(vec, index+1, S, no);
//         vector<int> yes = sub;
//         yes.push_back(S[index]);
//         subset(vec, index+1, S, yes);
//     }
    
    // 方法2
    void subset(vector<int> &S, vector<vector<int> > &vec, vector<int> sub, int start, int k) {
        if (k == sub.size()) {
            vec.push_back(sub);
            return;
        }
        for (int i = start; i < S.size(); ++i) {
            sub.push_back(S[i]);
            subset(S, vec, sub, i+1, k);
            sub.pop_back();
        }
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 364KB, 提交时间: 2021-04-30

class Solution {
public:
    void dfs(vector<int>& nums, vector<std::vector<int>>& res,
             vector<int>& sub, size_t len, size_t idx) {
        if (len == 0) {
            res.push_back(sub);
            return;
        }
        for (size_t i = idx; i < nums.size(); ++i) {
            sub.push_back(nums[i]);
            dfs(nums, res, sub, len-1, i+1);
            sub.pop_back();
        }
    }
    vector<std::vector<int> > subsets(vector<int>& nums) {
        vector<std::vector<int>> res;
        vector<int> sub;
        for (size_t i = 0; i <= nums.size(); ++i) {
            dfs(nums, res, sub, i, 0);
        }
        return res;
    }
};

详情