What would be the best way (in C) to get all sums of N numbers in an array, by using addition and subtraction?

For example (N = 3):

arr[] = [30, 14, 2]

results:
-30-14-2 = -46
-30-14 2 = -42
-30 14-2 = -18
-30 14 2 = -14
 30-14-2 = 14
 30-14 2 = 18
 30 14-2 = 42
 30 14 2 = 46

As can be seen, there are 2^N solutions.

I also noticed that the addition an subtraction symbols alternate in the same way as binary counting (000 001 … 110 111), which might be useful.

Probably a recursive approach would be best, but I find it very hard to think recursively.

Therefore, I hope someone can explain to me what the best strategy would be to tackle this problem.

——————————

EDIT:

I have a working Python code, but this uses sets set(), which aren’t available in C. (arr is an array containing all numbers.)

out = set()
out.add(0)
for i in range(0, len(arr)):
    tmp = set()
    for j in out:
        tmp.add(j   arr[i])
        tmp.add(j - arr[i])
    out = tmp
print(out)

——————————

EDIT:

With replacing the sets by arrays and making a few small changes, I got it working. Thanks to everyone who commented!

CodePudding user response：

This is a case where recursion seems preferable to a data structure because the exponential nature of the problem means thre's no risk of a stack overflow on any value of n you could realistically test, yet you can take advantage of the stack's implicit storage capabilities.

The recursive logic can be written very directly using an index i. The base case is when i >= n; print the sum you've accumulated. Otherwise, subtract the ith element from the sum and recurse on the rest of the numbers list without i. In a second branch, add the ith element to the sum and recurse on the rest of the numbers list without i.

Note that this procedure will include duplicate results, so if you want to eliminate those, your set idea is a good one.

It's generally poor design to mix IO and logic in functions, but for simplicity's sake, I'll break that rule here:

#include <stdio.h>

void print_possible_sums(int nums_len, int *nums, int sum, int i) {
    if (i >= nums_len) {
        printf("%d\n", sum);
    }
    else {
        print_possible_sums(nums_len, nums, sum - nums[i], i   1);
        print_possible_sums(nums_len, nums, sum   nums[i], i   1);
    }
}

int main() {
    int arr[] = {30, 14, 2};
    print_possible_sums(sizeof(arr) / sizeof(arr[0]), arr, 0, 0);
    return 0;
}

Output:

-46
-42
-18
-14
14
18
42
46

CodePudding user response：

I have made an algorithm that performs this problem. Maybe what I wrote is not as efficient as possible (so maybe it can be improved) but at least it works.

Let me know if it's okay.

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

#define MAX 4
void cycle(int arr[MAX]);
int toRepeat(int arr[MAX], int s);

int main(){
    int arr[MAX] = {1, 2, 3, 4};
    cycle(arr);
}

void cycle(int arr[MAX]){
    int a, ris;
    a = pow(2, MAX);
    for (int i= 0; i < a; i  ){
        ris = toRepeat(arr, i);
        printf(" = = \n", ris);
    }
}

int toRepeat(int arr[MAX], int s){
    int pos = 0;
    int ris = 0;
    int a;
    bool flag;
    a = pow(2, MAX);
    if (s < a/2) {
        ris  = arr[pos];
        printf(" %d", arr[pos]);
    } else {
        ris -= arr[pos];
        printf("-%d", arr[pos]);
    }
    pos  ;
    
    for (int i= 2; i < a; i = i * 2){
        for (int j= 0; j < i/2; j  ) {
            if (s%i == j) {
                ris  = arr[pos];
                printf(" %d", arr[pos]);
                pos  ;
                flag = true;
                break;
            }
        }
        if (!flag){
            ris -= arr[pos];
            printf("-%d", arr[pos]);
            pos  ;
        }
        flag = false;
    }
    return ris;
}

Output:

 1 2 3 4 =  10
 1-2 3 4 =   6
 1 2-3 4 =   4
 1-2-3 4 =   0
 1 2 3-4 =   2
 1-2 3-4 =  -2
 1 2-3-4 =  -4
 1-2-3-4 =  -8
-1 2 3 4 =   8
-1-2 3 4 =   4
-1 2-3 4 =   2
-1-2-3 4 =  -2
-1 2 3-4 =   0
-1-2 3-4 =  -4
-1 2-3-4 =  -6
-1-2-3-4 = -10