递归

递归是一种解决问题的方法，其中一个函数调用自身来解决子问题。每次调用函数时，问题规模通常会减小，直到达到一个基本情况（base case），这时直接返回结果。

题目描述

将一个正整数 ( n ) 分解为若干个大于 0 的整数之和，并按照字典序输出所有可能的分解方案。

输入描述

一个整数 ( n )（ 1 <= n <=15 ）。

输出描述

按照字典序输出所有方案。每个方案的数字之间用空格分隔。

数据范围

对于 ( 100\% ) 的数据，（ 1 <= n <=15 ）。

样例

输入样例

输出样例

样例解释

字典序是由数字的大小和顺序决定的，前面的数字越小，则字典序越小。例如：
- ( 1 1 1 1 ) 小于 ( 1 2 1 ) 小于 ( 2 1 1 ) 小于 ( 3 1 )。

思路

使用递归和回溯来生成所有组合。
通过控制选择的起始数字，确保每次选择都不重复并且有序。
当组合的和等于 ( n ) 时，记录下当前组合。

解题思路

我们需要将一个整数 ( n ) 分解为若干个大于 0 的整数之和，并且输出这些组合，要求按字典序排序。为此，我们可以采用递归和回溯的方法来生成所有的组合。

递归与回溯：通过递归的方式生成所有可能的组合，每次选择一个数字，并在达到条件时记录结果。回溯则是为了撤销选择，以便探索其他可能的组合。
字典序：通过控制选择的顺序，确保每次选择的数字从当前的起始数字开始，这样生成的组合自然按字典序排列。

代码解析

def backtrack(n, start, current, results):
    # 当当前和达到 n 时，输出当前组合
    if sum(current) == n:
        results.append(current[:])  # 记录当前组合
        return

base case: 如果当前组合的和等于 ( n )，就将这个组合记录到 results 中。使用 current[:] 创建一个当前列表的副本，防止后续修改影响结果。

    # 从 start 开始选择数字
    for i in range(start, n + 1):
        if sum(current) + i > n:  # 如果当前和加上 i 超过 n，结束循环
            break
        current.append(i)  # 选择 i
        backtrack(n, i, current, results)  # 递归
        current.pop()  # 回溯，撤销选择

选择数字: 从 start 到 ( n ) 遍历可能的数字 ( i )。
剪枝: 如果当前和加上 ( i ) 超过 ( n )，则不再继续循环，避免不必要的计算。
递归调用: 将 ( i ) 添加到 current 列表中，递归调用 backtrack 函数以继续选择下一个数字。
回溯: 通过 current.pop() 移除最后选择的数字，以恢复到上一步的状态，为下一轮选择做好准备。

def partition(n):
    results = []
    backtrack(n, 1, [], results)  # 从 1 开始选择
    results.sort()  # 按字典序排序
    for result in results:
        print(" ".join(map(str, result)))

初始化: 创建一个空的 results 列表来存储所有的组合。
开始回溯: 调用 backtrack 函数，从 1 开始选择。
排序与输出: 最后对结果进行排序（尽管通过选择顺序已经基本满足），并将每个组合格式化为字符串输出。

# 读取输入并调用函数
n = int(input())
partition(n)

输入: 从标准输入读取整数 ( n ) 并调用 partition 函数。

代码

def backtrack(n, start, current, results):
    # 当当前和达到 n 时，输出当前组合
    if sum(current) == n:
        results.append(current[:])  # 记录当前组合
        return

    # 从 start 开始选择数字
    for i in range(start, n + 1):
        if sum(current) + i > n:  # 如果当前和加上 i 超过 n，结束循环
            break
        current.append(i)  # 选择 i
        backtrack(n, i, current, results)  # 递归
        current.pop()  # 回溯，撤销选择

def partition(n):
    results = []
    backtrack(n, 1, [], results)  # 从 1 开始选择
    results.sort()  # 按字典序排序
    for result in results:
        print(" ".join(map(str, result)))

# 读取输入并调用函数
n = int(input())
partition(n)