有没有办法计算不同组的 n 个单位数整数加起来达到给定总和的数量？

Question

我想找到一种方法来计算（通过公式或代码）加起来达到给定总和 S 的 n 个数字的不同组合的数量 例如，3 位数字（从数字 1 到 9）的总和为 7 的组数（因此 n = 3，S = 7） 你得到： (1,3,4), (1,2,5), (2,5,1) 我怎样才能将其推广到任何总和以及任何n？ 我对编码或算法不太了解

我尝试过暴力破解，但失去了理智

Answer 1

是的，一种强力方法是使用递归函数简单地迭代所有可能的组合。最终，您将获得具有不同顺序的重复数字集的组合列表。您可以通过将列表中的每个组合转换为排序元组，然后有效地删除重复项来使数字组合唯一

这是Python的示例代码

def sumCombinations(n, s, combination, target):
    if n == 0:
        if s == target:
            return [list(combination)]
        else:
            return []

    ret = []
    for i in range(1, 10):
        combination.append(i)
        ret += sumCombinations(n - 1, s + i, combination, target) 
        combination.pop()
    
    return ret

print(sumCombinations(3, 0, [], 7))
# print output:
# [[1, 1, 5], [1, 2, 4], [1, 3, 3], [1, 4, 2], [1, 5, 1], [2, 1, 4], [2, 2, 3], [2, 3, 2], [2, 4, 1], [3, 1, 3], [3, 2, 2], [3, 3, 1], [4, 1, 2], [4, 2, 1], [5, 1, 1]]