（使用C语言详解）求一个集合的全部子集（leetcode编程笔记） |
您所在的位置：网站首页 › 集合真子集和子集的算法 › （使用C语言详解）求一个集合的全部子集（leetcode编程笔记） |
|
原题链接：子集 (Subsets) - 力扣 (LeetCode) 原码于文章末尾会给出。 本文通过位运算，实现题目要求，之后可能更新其他方法，敬请关注...... 题目： 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 ： 输入：{1，3，6，9} 输出：[] [1] [3] [1,3] [6] [1,6] [3,6] [1,3,6] [9] [1,9] [3,9] [1,3,9] [6,9] [1,6,9] [3,6,9] [1,3,6,9]具体步骤如下： 1. 首先，我们需要了解什么是集合的子集。集合的子集是指原集合中的元素可以任意个数（包括0个或全部）挑选出来组成的集合。 2. 对于一个有n个元素的集合，它的子集数量为2^n个。因此，我们需要遍历从0到2^n-1的所有数字，每个数字代表一个子集。 3. 利用位运算，我们可以很容易地得到一个数字表示的子集。例如，数字1的二进制表示为0001，它表示集合中的第一个元素；数字3的二进制表示为0011，它表示集合中的第一个和第三个元素。 4. 在遍历所有数字后，我们可以得到所有的子集。每个子集都是一个长度为n的数字序列，表示集合中的元素是否包含在当前子集中。 5. 最后，我们将所有子集输出即可。这里比较难的点在于，如何通过位运算得到我们想要的结果。 下面先将我们代码实现功能的主要函数列出来： void GetSubSet(int* num, int len, int tag) { int tmp; for (int i = 0; i < pow(2, len); i++) { tmp = tag; tag += 1; int is_first = 1; printf("["); for (int j = 0; j < len; j++) { if (tmp & 0x1) { if (is_first) { printf("%d", num[j]); is_first--; } else { printf(",%d", num[j]); } } tmp >>= 1; } printf("] "); } } 函数GetSubSet接受三个参数： int* num：指向整数数组的指针，该数组包含了要生成子集的元素。int len：整数数组的长度，即数组中元素的个数。int tag：用于跟踪当前生成子集的标记，初始时它被设置为0。 初始化：函数开始时，tag被设置为0，表示空集。 循环遍历所有子集：使用一个for循环，循环2^len次，每次循环代表一个子集。 重点来了 位运算：在每次循环中，使用tmp变量来暂存tag的值，然后通过tag += 1来计算下一个子集的tag。 这里实际上是在对tag进行二进制位操作，每次循环将tag的最低位设置为1， 然后通过tmp >>= 1将tag右移一位。 关于位运算这里可能理解比较困难，下面我将画图讲解。 刚开始的时候我们设置了输入集合的元素总个数n，这个n会在GetSubSet函数的位运算操作中生成n个二进制位。比如我们设置的n=4，那么我们下面就产生4个二进制位。 在遍历第一层第一次for循环时，临时变量tmp=0，即4位二进制都为0 0000在遍历第一层第二次for循环时，临时变量tmp=1，即4位二进制变为0001 0001以此类推...... 此时符合条件tmp & 0x1（意思是：用于检查变量 tmp 的最低位（二进制的第0位）是否为1。） is_first用于判断是否是第一次进入到这个for循环。 在遍历第一层第二次for循环时，临时变量tmp=1，即4位二进制变为0001，相对应的num[j]=子集元素中的第一个元素——1。 每执行完一次for循环，tmp >>= 1，也就是说tmp=0001会向右移动一位，变为000。 以上就是位运算的原理。 打印子集：在循环内部，使用另一个for循环来遍历数组num中的每个元素。如果当前tag的二进制表示中的第j位是1，说明元素num[j]应该被包含在子集中。如果这是子集列表中的第一个元素，则直接打印，否则打印逗号和元素。递归调用：虽然这段代码中没有递归调用，但这个思想可以用来生成子集树，每个子集都可以作为下一个子集的父集。这个算法的关键在于理解如何使用二进制数来表示和生成子集。每个子集都可以通过改变tag的某一位来得到下一个子集。当tag的某一位被设置为1时，表示对应数组元素被包含在子集中；当该位被设置为0时，表示对应元素不被包含。通过这种方式，我们可以遍历所有可能的子集。 实现代码： #define _CRT_SECURE_NO_WARNINGS #include #include #define MAX_SIZE 100 void GetSubSet(int* num, int len, int tag); int main() { int len; int num[MAX_SIZE]; while (scanf("%d", &len) && len != 0) { for (int i = 0; i < len; i++) { scanf("%d", num + i); } GetSubSet(num, len, 0); printf("\n"); } return 0; } void GetSubSet(int* num, int len, int tag) { int tmp; for (int i = 0; i < pow(2, len); i++) { tmp = tag; tag += 1; int is_first = 1; printf("["); for (int j = 0; j < len; j++) { if (tmp & 0x1) { if (is_first) { printf("%d", num[j]); is_first--; } else { printf(",%d", num[j]); } } tmp >>= 1; } printf("] "); } } |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |