How to compute the number of combinations with [1, N] that makes the combination sum equals to N?-CodePudding

when n = 1
S(1) = 1;

when n = 2, there are two combinations
2 = 2
2 = 1   1
S(2) = 2;

when n = 3, there are 3
3 = 3
3 = 1   1   1
3 = 1   2
S(3) = 3

4 = 4
4 = 1   1   1   1
4 = 2   1   1
4 = 2   2
4 = 3   1
S(4) = 5

…………

With n <= 1000, how to compute S(n)? I came out with a brute-force dfs solution, here is the code in python:

class S1:
    def __init__(self):
        self.cnt = 1

    def dfs(self, begin, n, remain):
        if n == 1: return
        if remain == 0:
            self.cnt  = 1
            return 
        if remain < 0:
            return 
        for i in range(begin, n):
            self.dfs(i, n, remain - i)

Is there some other ways not using recursion and have smaller time complexity to do this?

CodePudding user response：

A solution consists in defining a function f(s, d), corresponding to the number of combinations of sum s, with a maximum digit equal to or less than d.

Then, we can use the recursive relationship

f(s, d) = f(s, d-1)   f(s-d, d)

The first term f(s, d-1) corresponds to combinations with all terms less or equal to d-1, and the second term f(s-d, d) corresponds to the case where at least one element is equal to d.

One must take care of some special values:

 f(s, 1) = 1
 if (d > s) then f(s, d) = f(s, s)
 f(0,d) = 1

This can be implemented in an iterative way. This can be implemented equivalently in a recursive way. However, in the later case, it is important to use memorization in order to avoid calculating the same value several times.

The final answer is equal to

 S(n) = f(n, n)

The total complexity is O(n^2), which should be enough for a maximum size n = 1000.

What follows is an implementation in C to illustrate the algorithm. For n = 1000 for example, the solution is provided in about 10 ms.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

std::string toString(__int128 num) {
    auto neg = num < 0;
    if (neg) num = -num;
    std::string str;
    do {
        int digit = num % 10;
        str  = std::to_string(digit);
        num /= 10;
    } while (num != 0);
    std::string rev;
    if (neg) rev = "-"   std::string (str.rbegin(), str.rend());
    else rev = std::string (str.rbegin(), str.rend());
    return rev;
}

int main() {
    std::cout << "enter n: ";
    int n;
    std::cin >> n;
    std::vector<std::vector<__int128>> sums (n 1, std::vector<__int128> (n 1));
    
    for (int d = 0; d <= n; d  ) {
        sums[0][d] = 1;
    }
    for (int sum = 1; sum <= n; sum  ) {
        sums[sum][1] = 1;
        for (int d = 2; d <= sum; d  ) {
            int dp = std::min (sum-d, d);
            sums[sum][d] = sums[sum][d-1]   sums[sum-d][dp];
        }
    }
    std::cout << "S[" << n << "]= " << toString(sums[n][n]) << "\n";
    return 0;
}