递归
递归是一种解决问题的方法，其中一个函数调用自身来解决子问题。每次调用函数时，问题规模通常会减小，直到达到一个基本情况（base case），这时直接返回结果。
题目描述
将一个正整数 ( n ) 分解为若干个大于 0 的整数之和，并按照字典序输出所有可能的分解方案。
输入描述
- 一个整数 ( n )（ 1 <= n <=15 ）。
输出描述
- 按照字典序输出所有方案。每个方案的数字之间用空格分隔。
数据范围
- 对于 ( 100\% ) 的数据，（ 1 <= n <=15 ）。
样例
输入样例
4
输出样例
1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1
4
样例解释
- 字典序是由数字的大小和顺序决定的，前面的数字越小，则字典序越小。例如：
- ( 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)
