CODEWITHSUNDEEP
ccombinations
user1870171
user1870171

Reputation: 1

Combinations of given number that add up to X

Though it shouldn't be really difficult, I've been kind of stuck with this. I need to make a function in C, that computes and shows all the possible combinations (without repetition) of given number, where the digits (that only range from 1 to 9) of every combination give a specified sum when added.

I guess it's not the clearest explanation, so here is an example: Calculate all sets of 5 numbers (from 1 to 9) that add up to 28.

I would be really grateful, if someone could explain this.

Upvotes: 0

Views: 209

Answers (1)

John Dvorak
John Dvorak

Reputation: 27317

Since there are only 512 different choices, you could precompute the results easily.

To precompute:

  • Prepare an empty map(sum => set(set(digit))), named lookup.
  • for every subset of (1..9)
    • compute its sum.
    • If lookup does not have the key sum, create a new entry, an empty set.
    • add the subset to lookup[sum]

To lookup a sum:

  • if lookup has the key sum, return (a copy of) the entry. Else return an empty set.

To address some of the low-level-ness of C:

A map int=>x is simply an array. A set of x is simply an array + length too.

The array for the map can be allocated as static since you already know the largest key, 45.

You can pre-estimate the largest set of sets as well, or use dynamic allocation (more efficient). If you don't care about space, you can easily over-allocate (512 entries max.). I presume you don't want to over-allocate this much, so you could as well learn how to allocate dynamically.

A set of digits can be represented as a 9-bit bit mask (16 bits in memory). Then they're easy to enumerate.

A sketch of the actual type for lookup:

typedef setOfDigits int16;

struct setOfSets{
  setOfDigits* data;
  int16 count; //the actual amount of sets in the set
  int16 space; //the size of the allocated array
}

setOfSets lookup[46];

A sketch of the actual type for lookup, without dynamic allocation or structs:

int16 lookup[46][512];
int16 lookupLength[46];

Note that if you equate space:=count, then you never over-allocate, but you often re-allocate, which is easier to implement but potentially inefficient (but the code's run once, so hey)

Of course, high-level languages (and even C++) have dynamic arrays either natively (javascript) or through a standard library (C++, Java). In C, you have to rely on realloc.

Upvotes: 1

Related Questions