# Combinations based on 2 variables

What I'm trying to accomplish is making a function to the following:

Imagine that I have between 1-9 squares. Those squares have a number assigned to them globally, not individually. They are like a set, and that set has this number.

E.g.: | _ | _ | _ | 19

What I'm trying to do is a function that gives me the possible combinations depending on number of squares and the number associated with them. For the example above: 9, 8, 2 is one of the possible combinations. However I just want the numbers that are in those combinations, not the combinations themselves. Plus they have to be unique (shouldn't be 9, 9, 1). Oh and those numbers **range** from 1-9 **only**.

How can I achieve this in C? If you are wondering this is for a puzzle game.

Thanks in advance!

## Answers

For future reference, in combinatorics we say "order doesn't matter" to mean "I only want the set of numbers, not a specific ordering"

//Sets the given digit array to contain the "first" set of numbers which sum to sum void firstCombination(int digits[], int numDigits, int sum) { reset(digits, 0, 1, numDigits, sum); } //Modifies the digit array to contain the "next" set of numbers with the same sum. //Returns false when no more combinations left int nextCombination(int digits[], int numDigits) { int i; int foundDiffering = 0; int remaining = 0; for (i = numDigits - 1; i > 0; i--) { remaining += digits[i]; if (digits[i] - digits[i - 1] > 1) { if (foundDiffering || digits[i] - digits[i - 1] > 2) { digits[i - 1]++; remaining--; break; } else foundDiffering = 1; } } if (i == 0) return 0; else { reset(digits, i, digits[i - 1] + 1, numDigits - i, remaining); return 1; } } //Helper method for firstCombination and nextCombination void reset(int digits[], int off, int lowestValue, int numDigits, int sum) { int i; int remaining = sum; for (i = 0; i < numDigits; i++) { digits[i + off] = lowestValue; remaining -= lowestValue; lowestValue++; } int currentDigit = 9; for (i = numDigits + off - 1; i >= off; i--) { if (remaining >= currentDigit - digits[i]) { remaining -= currentDigit - digits[i]; digits[i] = currentDigit; currentDigit--; } else { digits[i] += remaining; break; } } }

Looks like you are trying to find a restricted Partition of the integer on the right. The link should give you a good starting place, and you should be able to find some algorithms that generate partitions of an integer into an arbitrary number of parts.

It sounds like what you're working on is very similar to kakuro, also know as Cross Sums: http://en.wikipedia.org/wiki/Cross_Sums

There are generators out there for these kinds of puzzles, for example: http://www.perlmonks.org/?node_id=550884

I suspect that most kakuro generators would have to solve your exact problem, so you might look at some for inspiration.