Find the number of possible sums which add to N using (1,...,K)

Question

I have the following problem to solve: given a number N and 1<=k<=N, count the number of possible sums of (1,...,k) which add to N. There may be equal factors (e.g. if N=3 and k=2, (1,1,1) is a valid sum), but permutations must not be counted (e.g., if N=3 and k=2, count (1,2) and (2,1) as a single solution). I have implemented the recursive Python code below but I'd like to find a better solution (maybe with dynamic programming? ). It seems similar to the triple step problem, but with the extra constraint of not counting permutations.

    
def find_num_sums_aux(n, min_k, max_k):
    
    # base case
    if n == 0:
        return 1
    
    count = 0
    # due to lower bound min_k, we evaluate only ordered solutions and prevent permutations
    for i in range(min_k, max_k+1):
        if n-i>=0:
            count += find_num_sums_aux(n-i, i, max_k)
    return count

def find_num_sums(n, k):
    count = find_num_sums_aux(n,1,k)
    return count

A low-effort way to add dynamic programming to your Python solution is to use `lru_cache` from `functools`. — hilberts_drinking_problem, Oct 17 '20 at 08:41
to avoid permutations generate them *ordered*. you essentially describe a coin change problem, with target sum N and coins of denominations 1,2,3,...,k. see e.g. [this answer](https://stackoverflow.com/a/27804489/849891) of mine. — Will Ness, Oct 17 '20 at 14:01

VFX · Accepted Answer · 2020-10-17T08:33:07.710

This is a standard problem in dynamic programming (subset sum problem).

Lets define the function f(i,j) which gives the number of ways you can get the sum j using a subset of the numbers (1...i), then the result to your problem will be f(k,n).

for each number x of the range (1...i), x might be a part of the sum j or might not, so we need to count these two possibilities.

Note: f(i,0) = 1 for any i, which means that you can get the sum = 0 in one way and this way is by not taking any number from the range (1...i).

Here is the code written in C++:

   

     int n = 10;
        int k = 7;
        int f[8][11];
        
        //initializing the array with zeroes
        for (int i = 0; i <= k; i++)
            for (int j = 0; j <= n; j++)
                f[i][j] = 0;
    
        f[0][0] = 1;
    
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j <= n; j++) {
                if (j == 0)
                    f[i][j] = 1;
                else {
                    f[i][j] = f[i - 1][j];//without adding i to the sum j
                    if (j - i >= 0)
                        f[i][j] = f[i][j] + f[i - 1][j - i];//adding i to the sum j
                }
            }
        }   
        
        cout << f[k][n] << endl;//print f(k,n)

Update
To handle the case where we can repeat the elements like (1,1,1) will give you the sum 3, you just need to allow picking the same element multiple times by changing the following line of code:

f[i][j] = f[i][j] + f[i - 1][j - i];//adding i to the sum

To this:

f[i][j] = f[i][j] + f[i][j - i];

In my problem, a sum may have equal factors. For instance, if N=3 and k=2, (1,1,1) is a valid sum. That was not explicitly mentioned in my original question and I have included it. AFAIK, the subset sum problem allows using each number from the set at most once, so it doesn't apply here. — Alan Evangelista, Oct 13 '20 at 12:42
I have just updated my answer to allow the duplication of elements @AlanEvangelista — VFX, Oct 17 '20 at 08:33

Find the number of possible sums which add to N using (1,...,K)

1 Answers1