C 语言递归生成子集代码详解及时间复杂度分析

#include <stdio.h>

// 递归函数，用于生成子集 void generateSubsets(int arr[], int size, int index, int subset[], int subsetSize) { // 输出当前子集 for (int i = 0; i < subsetSize; i++) { printf("%d ", subset[i]); } printf("\n");

// 递归终止条件
if (index >= size) {
    return;
}

// 递归生成子集
for (int i = index; i < size; i++) {
    // 添加当前元素到子集中
    subset[subsetSize] = arr[i];
    // 递归调用函数，生成剩余元素的子集
    generateSubsets(arr, size, i + 1, subset, subsetSize + 1);
    // 移除最后添加的元素，继续遍历下一个元素
    subset[subsetSize] = 0;
}

}

int main() { int arr[] = {1, 2, 3}; int size = sizeof(arr) / sizeof(arr[0]);

int subset[100];
int subsetSize = 0;

generateSubsets(arr, size, 0, subset, subsetSize);

return 0;

}

// 递归生成子集的思路是，对于给定的数组arr，从索引index开始遍历元素，逐个将元素加入到subset数组中， // 然后递归调用函数生成剩余元素的子集，直到遍历完所有元素。每次递归调用完成后，需要将最后添加的元素移除， // 然后继续遍历下一个元素，生成下一个子集。 // 时间复杂度：由于每个元素都有两种状态（加入子集或不加入子集），所以总的子集个数为2^size， // 每个子集的平均长度为size/2，因此时间复杂度为O(2^size * size/2) = O(2^size * size)。