回溯法C语言求集合的所有子集

好的，以下是一个基于回溯法的 C 语言程序，用于求一个集合的所有子集：

#include <stdio.h>

int n; // 集合的大小
int subset[100]; // 存放当前子集

void printSubset(int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", subset[i]);
    }
    printf("\n");
}

void solve(int k) {
    if (k == n) { // 已经枚举到所有元素
        printSubset(n);
        return;
    }

    // 不选第 k 个元素
    solve(k + 1);

    // 选第 k 个元素
    subset[k] = k + 1;
    solve(k + 1);
}

int main() {
    printf("请输入集合的大小：");
    scanf("%d", &n);

    solve(0);

    return 0;
}

程序中 `printSubset` 函数用于输出当前子集，`solve` 函数则是回溯算法的主体部分。

在 `solve` 函数中，`k` 表示当前正在处理的元素下标。对于每个元素，有两种选择：选或不选。

首先假设不选第 k 个元素，直接递归处理下一个元素，即 `solve(k + 1)`。

然后假设选第 k 个元素，将其加入当前子集中，并递归处理下一个元素，即 `solve(k + 1)`。

当递归到最后一个元素时，即 `k == n`，表示已经枚举到所有元素，此时调用 `printSubset` 函数输出当前子集。

最终在 `main` 函数中输入集合的大小，调用 `solve(0)` 开始求解。