c++ - Optimizing subset sum implementation

Question

I'm working on a solution to a variant of the subset sum problem, using the below code. The problem entails generating subsets of 11 ints from a larger set (superset) and check if it matches a specific value (endsum).

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

int endsum = 0, supersetsize = 0, done = 0;
int superset[] = {1,30,10,7,11,27,3,5,6,50,45,32,25,67,13,37,19,52,18,9};
int combo = 0;

int searchForPlayerInArray(int arr[], int player) {
    for (int i=0; i<11; i++) {
        if (arr[i] == player) {
            return 1;
        }
    }
    return 0;
}

int sumOfArray(int arr[]) {
    int res = 0;
    for (int i=0; i<11; i++) {
        res+=arr[i];
    }
    return res;
}

void printArray(int arr[], int arrSize) {
    for (int j=0; j<arrSize; j++) {
        printf("%2d ",arr[j]);
    }
    printf("= %d
",endsum);
}

void permute(int subset[], int pos, int sspos) {
    if (done) { //when a correct solution has been found, stop recursion
        return;
    }
    if (sspos == supersetsize) { // out of possible additions
        return;
    }
    if (pos == 11) { //is the current subset 11 ints long?
        int res = sumOfArray(subset);
        combo++;
        if (res == endsum) { //if the sum of the array matches the wanted sum, print
            printArray(subset,11);
            done = 1;
        }
        return;
    }
    for (int i=sspos; i<supersetsize; i++) {
        //assert(pos < 11);
        //assert(i+1 <= supersetsize);
        subset[pos] = superset[i];
        permute(subset,pos+1,i+1);
    }
}

int main(void) {
    endsum = 110;
    supersetsize = 20;
    int *arr;
    arr = malloc(supersetsize*sizeof(int));
    int i;
    for (i=0; i<supersetsize; i++) {
        arr[i] = 0;
    }

    permute(arr,0,0);

    printf("Combinations: %d",combo);
    return 0;
}

Although this solution works for small supersets (<15) it is slow and inefficient because it generates every possible permutation instead of just the unique ones. How can I optimize it to generate only unique subsets?

Edit: Complete source code added by popular demand.

Answer 1

I don't think there is a way to generate the unique subsets in better than exponential time.

To solve subset-sum efficiently you want to use dynamic programming. There are some pseudo-polynomial time algorithms for subset-sum that work this way. This Wikipedia article might help.