1

I am looking for an algorithmic approach to solving this general problem, where I have a set of integers, $S=\{0,1,2,3,4,5\}$ and I want to find the number of combinations of $i$ (say 7) integers from set $S$ that sum to $k$ (say 17). I am led to believe this is best solved with dynamic programming, but am uncertain how to begin.

Kenny Lau
  • 25,049
user3725021
  • 113

2 Answers2

3

We will denote the number of combinations as $f(i,k)$.

Base Case

We will consider $i=0$.

The sum of $0$ integers must be $0$ (empty sum).

So, if $k=0$, then the answer is $1$; otherwise, the answer is $0$.

Other Cases

Let us consider the first integer in the chosen combination. If it is $a$, then the other integers must sum to $k-a$.

Hence, we establish the relation $f(i,k) = \displaystyle \sum_{a \in S} f(i-1,k-a)$.

Optimization

The sum must be non-negative. Hence, $f(i,k) = 0$ for $k < 0$.

Also, the sum cannot exceed $i$ times the maximum element of $S$, so $f(i,k) = 0$ for $k > i\max(S)$.

If $k=0$, then there is only one way: $0+0+\cdots+0$, so $f(i,0) = 1$.

Application

Only a few steps will be shown for obvious reasons.

$$\begin{array}{cl} & f(7,17) \\ =& f(6,17) + f(6,16) + f(6,15) + f(6,14) + f(6,13) + f(6,12) \\ =& f(5,17) + 2f(5,16) + \cdots + 4f(5,10) + 3f(5,9) + 2f(5,8) + f(5,7) \\ =& f(4,17) + 3f(4,16) + \cdots + 10f(4,5) + 6f(4,4) + 3f(4,3) + f(4,2) \\ =& f(3,17) + 4f(3,16) + \cdots + 20f(3,0) + 10f(3,-1) + 3f(3,-2) + f(3,-3) \\ =& f(3,17) + 4f(3,16) + \cdots + 20 + 0 + 0 + 0 \\ =& \cdots \end{array}$$

The optimizations took place at the step when $i=3$. Of course, in reality, for a simple program, those expressions would never appear, which is when you need memoization. Another method would be to build up an array containing all intermediate values for a fixed $i$ which at step 1 is $0$, at step 2 is $1$, and so on until it reaches $i=7$.

Implementation

I have written a Python implemenation:

S = {0,1,2,3,4,5}
i = 7
k = 17

# this is in the step i=0, described in the base case
# where f(0,0)=1 and f(0,k)=0 for non-zero k
intermediates = [1] + [0]*k

for _ in range(i):
    temp = []
    for x in range(k+1):
        temp.append(sum(intermediates[x-s] if 0 <= x-s <= k else 0 for s in S))
    intermediates = [x for x in temp] # deep copy

print(intermediates[k])

The link to ideone is here.

Kenny Lau
  • 25,049
  • I think there is a flaw in your "other cases" part: "Hence, we establish the relation f(i,k)=∑a∈Sf(i−1,k−a)" I think some combinations in $f(i,k)$ are counted several times, for instance for $f(2,5)$ the set $(2,3)$ is counted twice (as $2$ added to the set $(3)$ from $f(1,3)$ and then as $3$ added to the set $(2)$ from $f(1,2)$... – Evargalo Jun 19 '17 at 06:52
  • @Evargalo I believe that $3+2$ and $2+3$ are considered two cases. – Kenny Lau Jun 19 '17 at 07:01
  • That's for the OP to clarify, but since he talked about "combinations", my understanding was that {2,3} and {3,2} are on and the same set... – Evargalo Jun 19 '17 at 07:21
2

Elements to complete Kenny Lau's answer - in case 2+3 and 3+2 are NOT considered as different combinations.

Other Cases

If $i>k$, obviously $f(i,k)=f(i-1,k)$.

If $i<=k$, then a solution in $f(i,k)$ without using integer $i$ is also a solution in $f(i-1,k)$ ; a solution using integer $i$ once is $(i)$ added to a solution in $f(i-1,k-i)$ ; a solution (if any is possible) using integer $i$ twice is $(i,i)$ added to a solution in $f(i-1,k-2i)$

Generally, if $q=k$ div $i$, i.e. $\exists r, 0<=r<k, k=qi+r$, then our recursive rule is:

$f(i,k)=\sum_{h=0}^q f(i-1,k-ih)$

Which can be incorporated in an algorithm similar to Kenny Lau's.

Evargalo
  • 2,593