创建一个 returns 所有 P 位数字的回溯程序，使得每 3 个连续数字总和为 S

Question

作为一个问题，我们的任务是编写一个递归回溯程序，打印所有数字为 P 的数字，使得该数字的每 3 个连续数字总和为 S。

我还不能制定递归回溯方法，但我能够用简单的循环和完整的搜索来创建一个。

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)

它是如何递归完成的？

Answer 1

这是一个简单且未优化的版本：

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, [])

您基本上在每个递归步骤中传递了最后 2 位数字 (last_2sum) 的总和，并且对于每个数字，检查是否 last_2sum + current_digit == S。唯一的例外是前 2 个索引，您只需循环所有 9/10 数字。

代码应该不难理解，但是从简短的描述中可以看出你有很多可以优化的地方。这里有几个：

您可以限制可能的数字范围。例如，如果 S == 20，在最后的数字中你肯定找不到数字 1。相反，如果 S == 8，最高位将是 8。
可以通过优化前2个索引来减少递归次数（几乎没有什么特别之处）
如果你运行这段代码，你会发现从第4位开始，前3位是重复的。这是一个巨大的优化。

创建一个 returns 所有 P 位数字的回溯程序，使得每 3 个连续数字总和为 S

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

python

recursion

search

loops

backtracking