recursive enumeration of integer subsets?

I have an NSArray of NSNumbers with integer values such as [1,10,3]. I want to get the sum of all the possible subsets of these numbers. For example for 1,10 and 3 i would get:

1, 10, 3, 1+10=11, 1+3=4, 10+3=13, 1+10+3=14

there are 2^n possible combinations. I understand the math of it but im having difficulties putting this into code. so how can i put this into a method that would take the initial array of numbers and return an array with all the sums of the subsets? e.g -(NSArray *) getSums:(NSArray *)numbers;

I understand that the results grow exponentially but im going to be using it for small sets of numbers.

A simple recursive solution - probably somewhat inefficient, and it's untested, but the general idea should be clear.

- (NSArray*)getSums:(NSArray*)numbers {
    return [[self getSumsHelper:numbers startingFrom:0] copy];
}

- (NSMutableArray*)getSumsHelper:(NSArray*)numbers startingFrom:(NSUInteger)index {
    /* (1) */
    if (index >= [numbers count])
        return [NSMutableArray arrayWithObject:[NSNumber numberWithFloat:0]];

    /* (2) Generate all the subsets where the `index`th element is not included */
    NSMutableArray* result = [self getSumsHelper:numbers startingFrom:index+1];

    /* (3) Add all the cases where the `index`th element is included */
    NSUInteger i, n = [result count];
    float element = [[numbers objectAtIndex:index] floatValue];
    for (i = 0; i < n; i++) {
        float element2 = [[result objectAtIndex:i] floatValue];
        [result addObject:[NSNumber numberWithFloat:element+element2]];
    }

    return result;
}

The key to the problem is to generate all the subsets of a given array. This can be done recursively by recognizing the following:

1. The set of subsets of an empty array is the empty array, and the sum of the elements in an empty array is zero. This is handled by the lines marked with (1).

2. If the array is not empty, then let the first element be X. Any subset either includes X or does not include it. Therefore, we will generate all the subsets of the array that does not include X (there's the recursion, marked by (2), calculate the sums of each subset, and then duplicate the array of sums and add X to each of the sums in the duplicated part (marked by (3)).

If you have only a handful of items in the original array (say, less than 16), then you can also count from 0 to 2ⁿ-1 in a for loop; each index will then correspond to a subset. The elements in the ith subset can be determined by writing i in base 2 and selecting those items from the array which correspond to a digit 1 in the base 2 form. I believe this is even less efficient than my solution above.

[Warning: "clever" code ahead. You are probably better off doing something simpler. But this is kinda fun and some of the techniques are worth knowing about.]

If the sets are small enough (which they'd better be, because otherwise you're going to run out of both memory and time), you could use the fact that subsets of an n-element set == n-bit numbers. So no need for recursion: loop from 0 to 1<

One drawback of that is that for each subset you potentially need to consider all its elements from scratch each time. So, next trick: use Gray code (http://en.wikipedia.org/wiki/Gray_code#Constructing_an_n-bit_Gray_code) so that set k has elements corresponding to the 1-bits in k^(k>>1). Now each subset differs from its predecessor in only a single bit, which you can isolate with another exclusive-or operation.

OK, but now you have a different problem: you have a power of 2 and want to know which element of the array that corresponds to. So see http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup and look at the bit beginning "If you know that v is a power of 2".

So the code ends up looking something like this (note: totally untested) ...

static const int bitPositions[32] = {
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

NSUInteger n = [numbers count];
NSUInteger lim = 1<<n;
NSUInteger k, prevSubset=0;
float prevSum = 0;
NSMutableArray * result = [NSMutableArray arrayWithCapacity: lim];
[result replaceObjectAtIndex: 0 withObject: [NSNumber numberWithFloat: prevSum]]; /* empty subset */
for (k=1; k<lim; ++k) {
  NSUInteger thisSubset = k^(k>>1);
  NSUInteger changed = thisSubset^prevSubset;
  int index = bitPositions[(changed * 0x077CB531U) >> 27];
  float delta = [[numbers objectAtIndex: index] floatValue];
  if (thisSubset&changed) prevSum += delta; else prevSum -= delta;
  [result replaceObjectAtIndex: k withObject: [prevsum floatValue]];
}

Further warning: Aside from being "clever" and therefore probably buggy and unmaintainable, the above accumulates any floating-point errors over the entire calculation. So if you're going to take this kind of approach, here's a better way (note: code is just as untested as the last lot):

static const int bitPositions[32] = {
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

NSUInteger n = [numbers count];
NSUInteger lim = 1<<n;
NSUInteger k;
NSMutableArray * result = [NSMutableArray arrayWithCapacity: lim];
[result replaceObjectAtIndex: 0 withObject: [NSNumber numberWithFloat: prevSum]]; /* empty subset */
for (k=1; k<lim; ++k) {
  NSUInteger firstOne = k & ~(k-1); /* one 1-bit (as it happens, the lowest) */
  NSUInteger predecessor = k^firstOne; /* what we get by removing firstOne */
  int index = bitPositions[(firstOne * 0x077CB531U) >> 27];
  float smaller = [[result objectAtIndex: predecessor] floatValue];
  float delta = [[numbers objectAtIndex: index] floatValue];
  [result replaceObjectAtIndex: k withObject: [(smaller+delta) floatValue]];
}

For a bit of extra efficiency, if you were really doing this you'd probably begin by building an array containing not the magic bit-indices of bitPositions above but the corresponding values from numbers, and thus saving one NSArray access per subset. If you care about efficiency then you should probably also copy numbers into a plain ol' C-style array of floats so that you aren't for ever having to call floatValue.