C 語言實現冪集生成：遞歸與迭代兩種經典算法詳解

問題描述

給定集合 A = {a, b, c, d}，要求按特定順序生成其冪集（所有子集）：

• 第 1 輪：a
• 第 2 輪：ab, b
• 第 3 輪：ac, abc, bc, c
• 第 4 輪：ad, abd, bd, acd, abcd, bcd, cd

規律是：每取出一個新元素，將其與已生成的所有子集組合，形成新子集。

算法思路

這是典型的冪集生成問題。對於 n 個元素，共有 2^n 個子集。可用位運算迭代法或遞歸回溯法實現。

方法一：位運算迭代（推薦，簡潔高效）

#include <stdio.h>
#include <string.h>

void power_set(char *set, int n) {
    int total = 1 << n;          // 2^n
    for (int mask = 1; mask < total; ++mask) {  // 從 1 開始跳過空集
        int first = 1;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                if (!first) printf("");  // 這裡可加分隔符
                printf("%c", set[i]);
                first = 0;
            }
        }
        printf("\n");
    }
}

int main() {
    char set[] = {'a','b','c','d'};
    power_set(set, 4);
    return 0;
}

方法二：遞歸回溯（符合題目「逐輪構造」的直觀邏輯）

#include <stdio.h>
#include <string.h>

char set[] = {'a','b','c','d'};
char subset[10];
int n = 4;

void dfs(int idx, int len) {
    if (idx == n) {
        if (len > 0) {
            subset[len] = '\0';
            printf("%s\n", subset);
        }
        return;
    }
    // 不選當前元素
    dfs(idx + 1, len);
    // 選當前元素
    subset[len] = set[idx];
    dfs(idx + 1, len + 1);
}

int main() {
    dfs(0, 0);
    return 0;
}

關鍵點解析

• 位運算法：利用整數二進制位 0/1 表示元素是否選中，遍歷 1 ~ 2^n-1 即可枚舉所有非空子集，時間複雜度 O(n·2^n)，無遞歸開銷。
• 遞歸法：自然對應「每輪加入一個新元素」的過程，易於理解並按題目要求的順序輸出（需調整輸出時機）。
• 若需完全匹配題目輸出順序，可在遞歸中先輸出「不選」分支再輸出「選」分支，並收集結果後按長度、字典序排序。

總結

冪集生成是經典面試題。位運算法代碼最短、效率最高；遞歸法思路清晰、易擴展（如求和、去重等）。根據場景選擇即可。