C语言 回溯法解决子集和数的问题

子集和问题是一个经典的组合优化问题，可以使用回溯法（backtracking）进行求解。具体的思路是：

1. 定义一个数组或者集合，存储所有可选的数值。
2. 定义一个数组或者集合，存储当前已选的数值。
3. 定义一个变量，记录当前已选数值的和。
4. 从第一个数开始，遍历可选数值，对于每个可选数值，判断是否可以加入已选数值中。如果可以，则加入已选数值中，更新当前和，并且递归调用解决剩余问题；如果不可以，则不加入已选数值中，继续遍历下一个可选数值。
5. 当已选数值的和等于目标值时，输出当前已选数值，结束递归。
6. 当所有可选数值都遍历完毕，仍未找到解，则回溯到上一个节点，继续遍历下一个可选数值。

下面是 C 语言实现的示例代码：

#include <stdio.h>

#define MAX_NUM 100

int nums[MAX_NUM];
int selected[MAX_NUM];
int sum, target;
int n;

void subset_sum(int k) {
    if (sum == target) {
        printf("Subset found: ");
        for (int i = 0; i < n; i++) {
            if (selected[i]) {
                printf("%d ", nums[i]);
            }
        }
        printf("\n");
        return;
    }
    if (k == n || sum > target) {
        return;
    }
    selected[k] = 1;
    sum += nums[k];
    subset_sum(k + 1);
    sum -= nums[k];
    selected[k] = 0;
    subset_sum(k + 1);
}

int main() {
    printf("Enter the number of elements: ");
    scanf("%d", &n);

    printf("Enter the elements: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }

    printf("Enter the target sum: ");
    scanf("%d", &target);

    subset_sum(0);

    return 0;
}

在实际应用中，为了避免重复计算，可以使用记忆化搜索或者动态规划进行优化。