专栏首页ACM算法日常leetcode题解 | 78. 子集

leetcode题解 | 78. 子集

里程碑:第一百篇文章

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

对于数组(1,2,3),所有的子集正好是Cn0+Cn1+Cn2+...+Cnn,算出来也就是2的n次方。

凡是和2的n次方扯上关系的算法题,貌似都可以用位运算来试试!

对于数组(1,2,3),如果用位来表示,可以看成是111,而000表示空集,也就是说0表示不存在,1表示存在。

这个解法以前的一篇文章有类似的思路。公众号现在发了一百来篇文章,也忘了是哪篇了。

对于集合中的任意元素x,如果x包含进来,就表示为1,不包含,就表示为0。

而从0到2n-1的每次迭代,都表示一次变化,每一次变化都是集合中的一种。

int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) {
    *returnSize = pow(2, numsSize);
    int **result;
    int *colSize;
    //分配二级指针,这块内存是一个数组,每个数组元素都是一个一级指针
    result = (int**)malloc(sizeof(int*) * (*returnSize));
    colSize = (int**)malloc(sizeof(int*) * (*returnSize));

    //计算出所有的组合
    //所有的组合也就是0-(2^n-1)的位形式
    //如3,0-7: [000, 001, 010, 011, 100, 101, 110, 111]
    for (int i = 0; i < *returnSize; i++) {
        int x = i;
        int count = 0;

        while (x) {
            if (x & 1)
                count++;
            x >>= 1;
        }

        colSize[i] = count;
        //分配大小,这个for循环的作用仅仅只是分配好大小
        result[i] = (int*)malloc(sizeof(int) * (colSize[i]));
    }

    *columnSizes = colSize;

    for (int i = 0; i < *returnSize; i++) {
        int x = i;
        int col = 0;
        int j = 0;

        while (x) {
            //如果哪一位上是1,就记录一下这个位置
            if (x & 1) {
                result[i][col++] = nums[j];
            }
            j++;
            x >>= 1;
        }
    }
    return result;
}

int main(int argc, char **argv)
{
    int i, j;
    if (argc <= 1) {
        fprintf(stderr, "Usage: ./test array...\n");
        exit(-1);
    }
    int size = argc - 1;
    int *nums = malloc(size * sizeof(int));
    for (i = 0; i < size; i++) {
        nums[i] = atoi(argv[i + 1]);
    }
    int *sizes;
    int count;
    int **lists = subsets(nums, size, &sizes, &count);
    for (i = 0; i < count; i++) {
        for (j = 0; j < sizes[i]; j++) {
            printf("%d ", lists[i][j]);
        }
        printf("\n");
    }
    return 0;
}

本文分享自微信公众号 - ACM算法日常(acm-clan)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 第 210 场周赛 解题报告

    那么在遍历过程中,栈中元素数量的最大值即为答案。栈中的(可以理解为还没遍历到匹配的),即那些嵌套的(。

    ACM算法日常
  • 图论建图

    图论建图无外乎邻接表建图和链式前向星建图,不要问我是怎么知道的,要是你的学校逼你打图论位的话你就知道了。

    ACM算法日常
  • 第八届福建省大学生程序设计竞赛 | FZU2280 Magic

    Kim is a magician, he can use n kinds of magic, number from 1 to n. We use strin...

    ACM算法日常
  • 一遍记住Java常用的八种排序算法与代码实现

    (如果每次比较都交换,那么就是交换排序;如果每次比较完一个循环再交换,就是简单选择排序。)

    田维常
  • 一遍记住Java常用的八种排序算法

    (如果每次比较都交换,那么就是交换排序;如果每次比较完一个循环再交换,就是简单选择排序。)

    Java旅途
  • ICPC Asia Shenyang 2019 Dudu's maze

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    用户2965768
  • LeetCode 第 210 场周赛 解题报告

    那么在遍历过程中,栈中元素数量的最大值即为答案。栈中的(可以理解为还没遍历到匹配的),即那些嵌套的(。

    ACM算法日常
  • LeetCode 164. Maximum Gap (排序)

    题解:首先,当然我们可以用快排,排完序之后,遍历一遍数组,就能得到答案了。但是快速排序的效率是O(n* logn),不是题目要求的线性效率,也就是O(n)的效率...

    ShenduCC
  • 图论--拓扑排序--判断一个图能否被拓扑排序

    拓扑排序的实现条件,以及结合应用场景,我们都能得到拓扑排序适用于DAG图(Directed Acyclic Graph简称DAG)有向无环图, 根据关系我们能得...

    风骨散人Chiam
  • Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

    Educational Codeforces Round 67 (Rated for Div. 2)

    用户2965768

扫码关注云+社区

领取腾讯云代金券