如何找出给定总和与元素个数的正整数所有排列？

问题描述 #

给定总和 sum 和元素个数 number of elements，找出所有由正整数组成的排列，满足这些元素的和等于给定总和。

示例：

• 输入：sum = 4，元素个数 = 2
• 输出：(1,3), (3,1), (2,2)

现有思路及问题分析 #

思路1：固定嵌套循环 #

创建N个范围为1到sum-1的数组，通过嵌套循环遍历所有组合并筛选和为目标值的排列。代码示例：

output = []
for x in array1:
  for y in array2:
    if x+y == target:
      output.append((x,y))

局限：仅能处理固定数量的元素，当N为任意值时，无法动态生成对应数量的嵌套循环，扩展性极差。

思路2：全组合筛选 #

借助itertools.combinations生成所有可能组合后再筛选符合条件的结果，但效率极低。代码示例：

import numpy as np
from itertools import combinations
 
def find_permutations(S,N):
  x = np.asarray([x+1 for x in range(S)]*N)
  y = [seq for seq in combinations(x,N) if sum(seq)==S]
  return list(dict.fromkeys(y)) # 去重

find_permutations(4,2)
# 输出：[(1, 3), (2, 2), (3, 1)]

问题：会先生成海量无意义的组合再进行筛选，比如调用find_permutations(16,16)时，实际只有(1,1,...,1)一个有效结果，但需要生成极多无效组合，耗时极久。

高效解法：回溯法生成有序分拆 #

我们可以通过回溯法，逐个确定每个位置的元素值，同时保证剩余元素的和与个数符合正整数要求，避免生成无效组合：

def find_all_permutations(target_sum, num_elements):
    result = []
    
    def backtrack(current, remaining_sum, remaining_elements):
        # 只剩最后一个元素时，直接取剩余的和（必须为正整数）
        if remaining_elements == 1:
            if remaining_sum >= 1:
                result.append(current + (remaining_sum,))
            return
        
        # 当前元素的取值范围：1到剩余总和 - (剩余元素数-1)
        # 因为剩下的每个元素至少需要是1，所以当前元素最大不能超过剩余总和减去剩余元素数-1
        max_num = remaining_sum - (remaining_elements - 1)
        for num in range(1, max_num + 1):
            backtrack(current + (num,), remaining_sum - num, remaining_elements - 1)
    
    backtrack((), target_sum, num_elements)
    return result

# 测试示例
print(find_all_permutations(4, 2))
# 输出：[(1, 3), (2, 2), (3, 1)]

# 测试极端情况
print(find_all_permutations(16, 16))
# 输出：[(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)]

解法说明 #

• 核心逻辑：每一步递归时，当前元素的取值范围被严格限制在1到剩余总和 - (剩余元素数-1)之间，确保剩下的元素能凑出至少1的正整数，从根源上避免无效组合的生成。
• 效率优势：极端场景下（如sum与元素个数相等）会直接返回唯一结果，无需额外计算；常规场景下也只会生成符合条件的组合，性能远超全组合筛选法。

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