如何用C语言通过加减运算获取数组元素所有组合的全部和值

方案1：二进制映射法（无需递归，符合你发现的规律） #

核心逻辑：N个元素对应2^{N种符号组合，每一种组合可以用0到2}N-1的整数的二进制位表示，比如第k位为0表示对应元素取减，为1表示取加，遍历所有整数即可计算出所有和值。

#include <stdio.h>

int main() {
    int arr[] = {30, 14, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int total = 1 << n; // 总组合数，等价于2^n

    for (int mask = 0; mask < total; mask++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            // 检查第i位，1为加，0为减
            if (mask & (1 << i)) {
                sum += arr[i];
            } else {
                sum -= arr[i];
            }
        }
        printf("%d\n", sum);
    }
    return 0;
}

运行后输出结果和你给出的8个测试值完全一致，逻辑直观好理解，不需要递归思维。

方案2：迭代递推法（和你写的Python代码逻辑完全对齐） #

核心逻辑：从初始和0开始，每遍历一个元素，就把之前所有的和分别加、减当前元素，生成新的和集合，和你将Python的set替换为数组的实现思路完全一致，C实现如下：

#include <stdio.h>
#include <stdlib.h>

int main() {
    int arr[] = {30, 14, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    // 最多有2^n个结果，预先分配空间
    int *res = (int*)malloc(sizeof(int) * (1 << n));
    int res_len = 1;
    res[0] = 0;

    for (int i = 0; i < n; i++) {
        int *tmp = (int*)malloc(sizeof(int) * res_len * 2);
        int tmp_len = 0;
        for (int j = 0; j < res_len; j++) {
            tmp[tmp_len++] = res[j] + arr[i];
            tmp[tmp_len++] = res[j] - arr[i];
        }
        free(res);
        res = tmp;
        res_len = tmp_len;
    }

    // 输出结果
    for (int i = 0; i < res_len; i++) {
        printf("%d\n", res[i]);
    }
    free(res);
    return 0;
}

如果需要去重，可以在每次生成tmp数组的时候加个查重逻辑，遍历已有的tmp元素判断是否已经存在，不存在再插入即可。

可选递归方案（参考用） #

核心逻辑：递归处理每个元素，每次分支为加当前元素、减当前元素两种情况，处理到最后一个元素时保存结果：

#include <stdio.h>
#include <stdlib.h>

void calc(int *arr, int n, int index, int current_sum, int *res, int *res_idx) {
    if (index == n) {
        res[*res_idx] = current_sum;
        (*res_idx)++;
        return;
    }
    // 加当前元素分支
    calc(arr, n, index + 1, current_sum + arr[index], res, res_idx);
    // 减当前元素分支
    calc(arr, n, index + 1, current_sum - arr[index], res, res_idx);
}

int main() {
    int arr[] = {30, 14, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int *res = (int*)malloc(sizeof(int) * (1 << n));
    int res_idx = 0;
    calc(arr, n, 0, 0, res, &res_idx);
    for (int i = 0; i < res_idx; i++) {
        printf("%d\n", res[i]);
    }
    free(res);
    return 0;
}

内容的提问来源于stack exchange，提问作者anon