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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏五分钟学算法

每天一算:Minimum Size Subarray Sum

leetcode上第209号问题:Minimum Size Subarray Sum

7710
来自专栏小L的魔法馆

C++创建学生类练习

38060
来自专栏灯塔大数据

每周学点大数据 | No.32优先队列

No.32期 优先队列 Mr. 王:我们回到这个问题中,如果是在内存中,我们只需要对前面的这些点做一个拓扑排序,就可以保证每一个节点在求解时,它们的所有入度...

311100
来自专栏python成长之路

集合常用操作

17940
来自专栏生信小驿站

R语言字符串处理①R语言字符串合并与拆分

35820
来自专栏章鱼的慢慢技术路

LeetCode_832. Flipping an Image_Solution

题目所描述的意思是对每个数组先进行取反,并且对数组中的每个元素进行取反转换,所以一共要执行两个操作。

9220
来自专栏九彩拼盘的叨叨叨

学习纲要:JavaScript 基础语法

12430
来自专栏西枫里博客

Python学习笔记十(lambda表达式)

lambda是一个表达式,并不像def一样定义一个复杂的函数,很简洁的一个代码块。通常被用来创建匿名函数。lambda的好处也很明显,首先省去了函数的定义过程,...

9420
来自专栏搞前端的李蚊子

JS使用循环按指定倍数分割数组组成新的数组的方法

 今天一个新人同事问了我一个问题,就是有一个像下边这种不知道具体长度的数组,想以每4个为一组,重新组合为一个二维数组,很简单的需求只需要用到一个循环再去取余数就...

49470
来自专栏书山有路勤为径

生成括号

已知n组括号,开发一个程序,生成这n组括号所有的合法的组合可能例如:n = 3 结果为:["((())) "," (()())","()(()) "," ()...

9210

扫码关注云+社区

领取腾讯云代金券