CODEWITHSUNDEEP
recursiondynamic-programming
Themistoklis Haris
Themistoklis Haris

Reputation: 365

Sum of integers with restrictrions

Getting right to the gist of the problem:

In how many ways can we add k positive integers to reach a sum of exactly n if each number is smaller or equal to given number m?

The problem is solvable with dynamic programming but I am stuck because I cannot find the optimal substructure or recursion for the solution.

Upvotes: 0

Views: 45

Answers (1)

uselpa
uselpa

Reputation: 18927

Here's a simple function in Python 3 that should fit your description. I assume that 0 is not an acceptable value but it's a trivial change if it is.

def howMany(k, n, m):

    def sub(pos, currentSum, path):
        if currentSum == n and pos == k: # reached the sum, print result and increase counter by 1
            print(path)
            return 1
        elif currentSum < n and pos < k: # still worth trying
            count = 0
            for i in range(1, m):
                count += sub(pos + 1, currentSum + i, path+[i])
            return count
        else: # abort
            return 0

    return sub(0, 0, [])

print(howMany(3, 10, 6))

yields

[1, 4, 5]
[1, 5, 4]
[2, 3, 5]
[2, 4, 4]
[2, 5, 3]
[3, 2, 5]
[3, 3, 4]
[3, 4, 3]
[3, 5, 2]
[4, 1, 5]
[4, 2, 4]
[4, 3, 3]
[4, 4, 2]
[4, 5, 1]
[5, 1, 4]
[5, 2, 3]
[5, 3, 2]
[5, 4, 1]
18

It could be optimised but that would obfuscate the logic at this stage.

Upvotes: 1

Related Questions