Print all the 3 consecutive digits that can be equal to a given number

Question

How can I write a recursive backtracking function count(N,S) in which it prints all N-digit numbers such that the sum of each 3 consecutive digits in the number is exactly equal to S where N will be less than or equal to 10, and is from 0 to 27.

Code:

def count(S):
    n = int(S)
    if n % 3 == 0:
        print(int(n / 3 - 1),int(n / 3),int(n / 3 + 1))
    else:
        print(None)
S = 27
count(S)

Sample Output:

8 9 10

I'm quite confused on how can I write this recursively.

Answer 1

Your current function is not recursive. To make it recursive, you'd basically have to call count(n-1, s) somewhere within the execution of count(n, s). One way to do it would be like this:

• if n > 1, get possible solutions for n-1 and append any digit that still satisfied the condition
• if n == 0 just return "" (it's a bit easier if the function returns strings, not actual integers)

As a generator function, this could look somewhat like this. Of course, you can just as well collect the results in a list and return them, or just get the count of such numbers and return that.

def count(n, s):
    if n > 0:
        for x in count(n-1, s):
            for d in range(10):
                y = str(d) + x
                if len(y) < 3 or sum(map(int, y[:3])) == s:
                    yield y
    else:
        yield ""

for x in count(5, 15):
    print(x)