Combinations of integers adding up to a specific number

Question

I need a program for all the combinations of the alphabet "01234", of length 5, of which the digits add up to 4 or less.

Examples 00013, 00031, 00101, 10120

but not 11213, 00341

Questions:

How to calculate the number of strings that add up to X ?
How to generate all strings that add up to X ?
How to generate all strings that add up to a number <=X ?
What is this concept called in mathematics ? update:
How to find the subset(s) of digits (numbers) that add to sum X ?

Any procedural language or pseudo code will do. By concept I mean finding the subset(s) of numbers that will add up to a given sum. So, in addition I would like to get an algorithm to find these subsets. Finding all combinations and then filtering out the ones that match is easy, but not time efficient for larger alphabets (strings of digits).

You can do this with five nested `for` loops, or one [Cartesian Product](http://en.wikipedia.org/wiki/Cartesian_product). — Kevin, Aug 07 '14 at 20:00
@Edward I already had a solution to generate all combinations. I put that in Excel and filtered it. Then I had the solution, but not a flexible, efficient program. — Michiel van der Blonk, Aug 08 '14 at 00:32
Some googling gave me the concepts "sumset problem", "same set problem", "count the coins problem" and "knapsack problem". It seems to me my problem is equivalent to a knapsack problem with a size of 4 and a set of {1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4} However, the knapsack problem is defined to find one efficient solution, not all solutions! — Michiel van der Blonk, Aug 08 '14 at 00:33

score 2 · Answer 1 · edited May 23 '17 at 10:29

Suppose you want all combinations(it seems more like permutations from your question, because you listed both 00013 and 00031) that sum up to 4, I think first you need a number partition program to partition the sum 4 into parts, and extend each partition's length into 5 by adding zeros, like this:

1, 1, 1, 1   ->    1, 1, 1, 1, 0
1, 1, 2      ->    1, 1, 2, 0, 0
1, 3         ->    1, 3, 0, 0, 0
2, 2         ->    2, 2, 0, 0, 0
4            ->    4, 0, 0, 0, 0

then you can do permutation on each of them. Because there are many duplicates in the number, the total number of permutations are not that big, for example, 1,1, 1, 1, 0 have only 5 permutations, 11110, 11101, 11011, 10111, 01111.

on how to do number partition, you can check out here, as for permutation, as I am a C++ programmer, I would use the next_permutation function in STL library, or check out here.

This method is pretty generic, you can deal with combinations of any sum without deep loop.

Excellent. Number partitioning was the term I was looking for. In general once you know what something is called it's very easy to Google it. — Michiel van der Blonk, Aug 09 '14 at 03:03

score 0 · Answer 2 · answered Aug 07 '14 at 21:29

Here is a quick and dirty one. I am sure you will find ways to make it more effective. The code uses arrays instead of strings.

// Calculate sum of all digits
func numsum(a: [Int]) -> Int {
    return reduce(a, 0, { $0 + $1 })
}

// Maximum number allowed
let maxnum = 4

// Number of digits
let arlen = 5

// Number we are looking for
let reqnum = 4

// Array that holds the combinations
var a = Array(count: arlen, repeatedValue: 0)

// Array where we keep all positive results
var b = [[Int]]()

// Function to go over all combinations and storing those that add up to the number we are looking for
// Called recursively for each level starting with 0

func addNum(level: Int = 0) {
    if level == arlen {
        return
    }

    a[level] = 0
    while a[level] <= maxnum {
        //println(a)
        if numsum(a) == reqnum {
            b.append(a)
        }
        else {
            addNum(level: level + 1)
        }
        a[level] += 1
    }
}
// Calling the function
addNum()

// Printing it out so that it looks like strings
for arr in b {
    for n in arr {
        print(n)
    }
    println()
}

Is this the SWIFT programming language? – Michiel van der Blonk Aug 07 '14 at 22:04 — Michiel van der Blonk, Aug 07 '14 at 22:04

score 0 · Answer 3 · 2014-08-08T00:04:25.017

0

Other Q&D solution, in Python

for a in range(5):
    for b in range(5):
        for c in range(5):
            for d in range(5):
                for e in range(5):
                    if a + b + c + d + e <= 4:
                        print a, b, c, d, e

You can replace the <= by ==, or the print by a N+= 1.

There are 70 "arrangements with repetition" giving sum 4, and126 with sum <= 4.

edited Aug 08 '14 at 00:04

answered Aug 07 '14 at 23:51

Thanks for this short code. However, by concept I meant the concept of finding the numbers of a set that add to a specific sum. When using only those subsets the programming would be way more efficient. – Michiel van der Blonk Aug 08 '14 at 00:06

score 0 · Answer 4 · answered Aug 08 '14 at 01:30

(Composition) is a good starting point. It gets complicated by allowing zeros (which requires considering orderings).

Though the zeros complicate it, and you'd probably have to ask on math stack to be able to get a general formula as combinatorics can get rather tricky. Otherwise, the other answers are sufficient your question.

score 0 · Answer 5 · answered Aug 08 '14 at 17:58

I believe that recursive code is short and clear. It outputs combinations in lexicographic order, without redundant work.

  procedure Combine(Digits, Sum, AMax: Integer; CurrentValue: string);
    if Digits = 0 then 
      output(CurrentValue)
    else
      for i := 0 to Min(Sum, AMax) do 
        Combine(Digits - 1, Sum - i, AMax, CurrentValue + IntToStr(i));

//usage
  Combine(4, 3, 3, '');

output:
0000 0001 0002 0003 0010 0011 0012 0020 0021 0030 0100 0101 0102 0110 0111 0120 0200 0201 0210 0300 1000 1001 1002 1010 1011 1020 1100 1101 1110 1200 2000 2001 2010 2100 3000

Combinations of integers adding up to a specific number

5 Answers5