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

Answer 1

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];