Create a backtracking program that returns all P-digit numbers such that every 3 consecutive digit sums up to S

Question

As a problem, we're tasked to write up a recursive backtracking program that prints all numbers with P digits such that every 3 consecutive digit of that number sums up to S.

I cannot formulate a recursive backtracking approach yet, but I was able to make one with simple loops and complete search.

def count(P, S):
    if P >= 3:
        for number in range(10**(P-1), (10**P)):
            string = str(number)      # I converted it to string to easily access every digit of the number.
            isEqual = True
            for digit in range(0, len(str(i))-2):
                if int(string[digit]) + int(string[digit + 1]) + int(string[digit + 2]) != S:
                    isEqual = False
                    break
            if isEqual: print(i)

How is it done recursively?

Answer 1

This is a simple and unoptimized version:

max_digits = 5
tot_sum = 12

max_digit = 9
min_digit = 0
    
digits = {x for x in range(min_digit, max_digit + 1)}

def print_valid_number(cur_digit_i, max_digits, tot_sum, last_2sum, digits, cur_num):
    if cur_digit_i == max_digits:
        print(''.join(map(str, cur_num)))
        return
    
    cur_digits = set(digits)
    if cur_digit_i == 0 and 0 in cur_digits:
        cur_digits.remove(0)
        
    for d in cur_digits:
        if last_2sum + d == tot_sum or cur_digit_i == 0 or cur_digit_i == 1:
            cur_num.append(d)
            next_last_2sum = d + (0 if cur_digit_i == 0 else cur_num[cur_digit_i - 1])
            print_valid_number(cur_digit_i + 1, max_digits, tot_sum, next_last_2sum, digits, cur_num)
            cur_num.pop()
    
print_valid_number(0, max_digits, tot_sum, 0, digits, [])

You basically pass the sum of the last 2 digits (last_2sum) on each recursive step and, for each digit, check if last_2sum + current_digit == S. The only exception are the first 2 indexes where you just loop all 9/10 digits.

Code should not be hard to understand, but from the brief description, it is clear that you have many doable optimizations. Here few of them:

• You could limit the range of possible digits. For instance, if S == 20, in the final number you are definitely not going to find the digit 1. Conversely, if S == 8, the highest digit is going to be 8.
• You can reduce the number of recursions by optimizing the first 2 indexes (it is almost unremarkable)
• If you run this code, you will find that from the 4th digits, the first 3 ones are repeating. This is a huge optimization.