如何在Python中通过回溯法正确返回结构化解决方案？

一、N皇后问题修改方案 #

当前修改后的N皇后代码返回扁平列表，核心问题是基准条件返回单个列表且用extend打散递归结果，调整后可返回分组的二维解：

修改后的代码 #

def n_queens(n, board=[]):
    if n == len(board):
        # 返回包含当前board副本的列表，避免后续pop修改已保存的解
        return [board.copy()]

    result = []
    for col in range(n):
        board.append(col)
        if is_valid(board):
            # 直接合并递归返回的解列表，保持子列表结构
            result.extend(n_queens(n, board))
        board.pop()
    return result

def is_valid(board):
    current_queen_row, current_queen_col = len(board) - 1, board[-1]
    for row, col in enumerate(board[:-1]):
        diff = abs(current_queen_col - col)
        if diff == 0 or diff == current_queen_row - row:
            return False
    return True

print(n_queens(4))  # 输出 [[1,3,0,2],[2,0,3,1]]

修改要点 #

• 基准条件调整：找到合法解时返回[board.copy()]，而非直接返回board。因为board是可变对象，后续pop操作会修改原列表，必须复制当前状态保存。
• 结果收集：递归返回的是包含解的列表，用extend直接合并这些子列表，最终得到二维结构。

二、单词拆分问题修改方案 #

当前单词拆分代码返回扁平列表，是因为基准条件返回空列表且直接拼接单词导致结构丢失，调整后可返回每个拆分路径的结构化列表：

修改后的代码 #

def back_track(string, word_set):
    if len(string) == 0:
        # 返回包含空列表的列表，标记一个完整拆分路径的结束
        return [[]]

    paths = []
    for i in range(1, len(string)+1):
        prefix = string[:i]
        if prefix in word_set:
            # 将当前单词与后续每个合法路径组合，形成完整拆分
            for sub_path in back_track(string[i:], word_set):
                paths.append([prefix] + sub_path)
    return paths

print(back_track(string="bedbathandbeyond", word_set={"bed", "bath", "bedbath", "and", "beyond"}))
# 输出 [['bed','bath','and','beyond'],['bedbath','and','beyond']]

修改要点 #

• 基准条件调整：字符串为空时返回[[]]，代表一条完整拆分路径的终止（空列表作为路径结尾标记）。
• 路径组合：不再直接拼接单词，而是遍历递归返回的子路径，将当前单词添加到子路径开头，生成完整拆分路径后加入结果列表，保留层级结构。

内容的提问来源于stack exchange，提问作者daultimateboss