Find all variations of a digit sum

Question

Can anyone please direct me to an algorithm/formulae that says how to calculate all variations of a digit sum with a certain upper limit

So for example, if my digit sum is 6 and the upper limit is 123, then all variations for that digit sum would be: 6, 15, 24, 33, 42, 51, 60, 105, 114 and 123.

The upper limit can be up to 10**18 and program needs to work in under 1 second(in C/CPP), so brute force is not an option.

Answer 1

I think there is a recursive approach to solve this problem: consider a procedure int f(bool limit, int bit_count, int bit_sum), which calculates the number of variations that are no longer than bit_count bits that have a bit sum of bit_sum. The bool parameter limit denotes whether the limit (in your example, 123) takes effect.

Suppose Limit[i] denotes the i-th bit of the limit.

int f(bool limit, int bit_count, int bit_sum){
    if(bit_sum < 0)
        return 0;
    if(bit_count == -1)
        if(bit_sum == 0)
            return 1;
        else
            return 0;

    int ans = 0;
    for(int i = 0; i <= limit ? Limit[bit_count] : 9; i++){
        ans += f(limit && i == Limit[bit_count], bit_count - 1, bit_sum - i);
    }
    return ans;
}

In your example of bit sum as 6 and upper limit as 123, Limit[2] = 1, Limit[1] = 2, Limit[0] = 3. The answer is f(true, 2, 6).

For the sake of quick, you can convert this recursive approach into a dynamic programming approach by a record table. The time complexity of the corresponding DP approach is O(bit_sum * log(upper_limit)). I think this speed can meet your 1 second requirement.