Thread: How can this code be improved? Subset sum in C

I got this problem with subset sum, in which as the term says, i need to find all numbers that combined gives a certain number S. The problem is that I need to combine both + and -. The problem itself is as follows:

A set of natural numbers is given. Generate all the subsets of this set joined by alternating + and - operators which sum up to exactly S. .
I/O description. Input: enumeration of elements in the set, on one line, then sum on one line e.g.
1 3 5 7 2 6
0
Output: enumeration of elements resulting in the given sum, e.g.
1-3+2
1+3-6
5-7+2
1+5-6
...

For starters, I did the simple subset sum, the following code:

Code:

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#define NMAX 10

void display(int res[],int k){
    int i;
    printf("\n");
    for(i=0; i<=k; i++){
        printf("%d ",res[i]);
    }
}

int partial_sol(int y[],int m,int s){
    int i=0, sum=0;
    for(i=0; i<=m; i++){
        sum+=y[i];
    }
    if(sum<=s){
        return1;
    }
    return0;
}

int complete_sol(int y[],int m,int s){
    int i=0, sum=0;
    for(i=0; i<=m; i++){
        sum+=y[i];
    }
    if(sum==s){
        return1;
    }
    return0;
}

void backtrack(int k,int n,int s,intset[],int res[]){
    int j;
    for(j=k; j<n; j++){
        res[k]=set[j];
        if(partial_sol(res, k, s)==1){
            if(complete_sol(res, k , s)==1){
                display(res, k);
            }
            elseif(k<n)
                backtrack(k+1, n, s,set, res);
        }
    }
}

void main(){
    int n, s, i;
    printf("No. of elements: ");
    scanf("%d",&n);
    printf("\n Sum: ");
    scanf("%d",&s);
    intset[n],res[n];
    for(i=0; i<n; i++){
        printf("Elem no. %d: ", i);
        scanf("%d",&set[i]);
        res[i]=0;
    }
    backtrack(0, n, s,set, res);
}

I got several ideas on how to resolve this, like for example, if it is possible for C to see the numbers as both positive or negative integers, i don't know if that can be implemented, maybe something like a complement of the numbers? Any other ideas would be much appreciated.

Here too -> dynamic programming - How can this code be improved? Subset sum in C - Stack Overflow

Code:

void main()

"main()" returns int, not void: FAQ > main() / void main() / int main() / int main(void) / int main(int argc, char *argv[]) - Cprogramming.com

These combinatorics problems can be simplified quite a bit, if you realize you can form all possible combinations of subsets N terms, if you precede each term with an operator, and include an operator ignore. Here, you'd have three operators: +, -, and ignore, so for N terms, there are 3^N-1 possible subsets. (The -1 is because of the subset with all operators ignore that always yields zero.)

If you calculate combinations = 3^N, then you can loop from 1 to combinations-1, inclusive, and trivially find the sum of each subset. If i is the number of the subset, and 0 refers to ignore, 1 refers to +, and 2 refers to -, then i%3 is the operator for the first term, (i/3)%3 is the operator for the second term,((i)/3)/3)%3 = (i/9)%3 is the operator for the third term, and so on.

The entire problem is solved using a simple double loop.

Originally Posted by Nominal Animal

These combinatorics problems can be simplified quite a bit, if you realize you can form all possible combinations of subsets N terms, if you precede each term with an operator, and include an operator ignore. Here, you'd have three operators: +, -, and ignore, so for N terms, there are 3^N-1 possible subsets. (The -1 is because of the subset with all operators ignore that always yields zero.)

If you calculate combinations = 3^N, then you can loop from 1 to combinations-1, inclusive, and trivially find the sum of each subset. If i is the number of the subset, and 0 refers to ignore, 1 refers to +, and 2 refers to -, then i%3 is the operator for the first term, (i/3)%3 is the operator for the second term,((i)/3)/3)%3 = (i/9)%3 is the operator for the third term, and so on.

The entire problem is solved using a simple double loop.

I understand what you are saying I think, but I cannot figure out how to write it in code.