力扣(LeetCode)78. 子集(C语言)_leetcode78

一、环境说明

1. 本文是 LeetCode 78题 : 子集，使用c语言实现
2. 一题双解。
3. 测试环境:Visual Studio 2019

二、代码展示

2.1 01编码

// 两种思路:
// 递归//深度优先//回溯
// 01编码，迭代求解。
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    //长度n的集合，子集个数为2的n次方-1.
    int row = 1<<numsSize;
    int **ans = (int**)calloc(row,sizeof(int*));
    *returnSize = row;
    *returnColumnSizes = (int*)calloc(row,sizeof(int));//一共2的n次方行
    int *path=(int*)calloc(numsSize,sizeof(int));//子序列
    //01编码，迭代求解。
    for(int i = 0;i<(1<<numsSize);i++){
        int column=0;//列数
        for(int j =0;j<numsSize;j++){
            if(i&(1<<j)){//对i的每一位尝试构造子集
                path[column++]=nums[j];//如果i的第j个二进制位是1,则nums[j]元素入路径path。
            }
        }
        int *temp = (int*)calloc(column,sizeof(int));
        memcpy(temp,path,column*sizeof(int));
        returnColumnSizes[0][i]=column;
        ans[i]=temp;
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2.2 回溯

int **ans;
int *ansColumnSize;
int ansSize;

int *path;
int pathSize;
void dfs(int cur,int nums[],int numsSize){
    if(cur == numsSize){//构成了一个子集//保存，弹栈
        int *temp = (int*)calloc(pathSize,sizeof(int));
        memcpy(temp,path,pathSize*sizeof(int));
        ansColumnSize[ansSize] = pathSize;//路径大小入答案
        ans[ansSize++]=temp;//ans[ansSize]指向当前路径,答案规模++
        return;
    }
    //递归体编写
    path[pathSize++] = nums[cur];//尝试所有可能
    dfs(cur+1,nums,numsSize);//一路向前
    pathSize--;//回溯
    dfs(cur+1,nums,numsSize);
}
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    ans = malloc(sizeof(int*) * (1 << numsSize));
    ansColumnSize = malloc(sizeof(int) * (1 << numsSize));
    path = malloc(sizeof(int) * numsSize);
    *returnSize = 1 << numsSize;
    ansSize = pathSize = 0;
    dfs(0, nums, numsSize);
    *returnColumnSizes = ansColumnSize;
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

三、思路分析

3.1 01编码思路

• 01编码与集合性质说明：

1. 对于一个集合，元素个数为n。我们可以把它的每个位置采用01编码，集合本身所有位是1，说明它包含集合的全部元素。让集合某些位置为0，构成缺少这些位置的子集。
2. 利用了集合的性质，一个集合，大小为n，对应子集的数量是Cn-1+Cn-2+…+Cn-n=2的n次方-1。任何大小为n个集合都有这个性质。

• 利用上述性质，我们只需要二重循环：
• ①遍历2的n次方-1
• ②对每个数遍历它的每个二进制位，一个数二进制位是n位。
• 加入if(i&(1<<j))判断，执行操作，就能得到每一种子集的构造。

3.2 回溯法思路

• 回溯法，就是在一路向前的递归基础上，在每一步递归后，回退一步，选择下一个元素，再次递归。
• 在集合，排列的问题里，回溯法用的特别多。还不熟练的读者，多刷排列组合题目，思路会理解的，模板也会背会的。

四、代码分析

• 理解思路很重要！
• 博主欢迎读者在评论区留言，作为日更博主，看到就会回复的。

五、AC

六、复杂度分析

6.1 01编码复杂度

1. 时间复杂度:$O(n\times 2^n)$ ,n是nums数组的大小。遍历$2^n$个数，同时对一个数的每一位尝试构造子集的时间复杂度是$O(n\times 2^n)$
2. 空间复杂度:$O(n)$,使用了path，用于暂存子集。

6.2 回溯复杂度

1. 时间复杂度:$O(n\times 2^n)$，一共$2^n$种可能，对每一种可能构造子集的时间开销是$O(n)$，回溯的时间复杂度是$O(n\times 2^n)$。
2. 空间复杂度:$O(n)$,使用了path，用于暂存子集。