【算法设计与分析】将数字分解为n个数字之和

大家好，欢迎来到IT知识分享网。

【例】数字6可分解为

6

5+1

4+2        4+1+1

3+3        3+2+1         3+1+1+1

2+2+2    2+2+1+1    2+1+1+1+1

1+1+1+1+1+1

思路：回溯算法，搜索所有情况，只保留符合条件的

递归终止条件：临时数组求和等于n则加入结果集，同时结束递归

递归过程：循环遍历1..n，将新数字加入临时数组中进入下一层递归，出来后再将其移除

回溯的关键在于，添加和移除，保证所有可能性都被遍历到，整体结构和栈类似

代码

# 结果集（解空间），全局变量保存最终结果 result_set = [] def foo(n, result=None): """n为要分解的数字的2倍，result为临时结果""" if result is None: result = [] # 当n正好与result中元素求和相等时把result作为一种解，添加到解空间result_set中 if n == sum(result): global result_set # 对result进行排序是为了方便判断解空间result_set中是否包含result sorted_result = sorted(result[:], reverse=True) # 只有在结果集中不含result才将其加入解空间，确保每个结果的唯一性 if sorted_result not in result_set: result_set.append(sorted_result) else: # 从1..n把所有数字相加的所有情况列出来 for i in range(1, n): # 为了提高效率， # 对于(result + i) > (n - i)时直接回溯，因为继续执行result只会递增，不再可能等于n if sum(result) + i > n - i: break result.append(i) foo(n - i, result) result.pop() def combination_sum(n): foo(2 * n) return result_set if __name__ == '__main__': res = sorted(combination_sum(6)) print(res) # 打印结果：[[1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1], [2, 2, 1, 1], [2, 2, 2], [3, 1, 1, 1], [3, 2, 1], [3, 3], [4, 1, 1], [4, 2], [5, 1], [6]] # 为了方便验证结果，将结果格式化输出 res_size = len(res) for i in range(res_size - 1, -1, -1): if i + 1 < res_size and int(res[i][0]) != int(res[i + 1][0]): print('') res[i] = list(map(lambda x: str(x), res[i])) print('+'.join(res[i]), end=' ') # 打印结果： # 6 # 5+1 # 4+2 4+1+1 # 3+3 3+2+1 3+1+1+1 # 2+2+2 2+2+1+1 2+1+1+1+1 # 1+1+1+1+1+1