leetcode题解 | 78. 子集

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

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;
}