algorithm - 有没有一种方法可以计算 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()
    
    ret = [tuple(sorted(x)) for x in ret]
    ret = set(ret) # remove duplicates
    ret = [list(x) for x in ret]
    return ret
        
lst = sumCombinations(3, 0, [], 7)
print(lst)
# output: [[1, 1, 5], [1, 3, 3], [2, 2, 3], [1, 2, 4]]

编辑:如果您希望数字是唯一的，可以添加额外的索引来跟踪递归函数中允许的最小索引

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

    ret = []
    for i in range(index, 10):
        combination.append(i)
        ret += sumCombinations(n - 1, s + i, i + 1, combination, target) 
        combination.pop()
    
    return ret
        
lst = sumCombinations(3, 0, 1, [], 7)
print(lst)
# output: [[1, 2, 4]]

或者，如果您想以不同的顺序保留重复的数字集，您可以跟踪 bool 数组来查看该数字是否已被使用，而不是索引

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

    ret = []
    for i in range(1, 10):
        if used[i]:
            continue
        combination.append(i)
        used[i] = True
        ret += sumCombinations(n - 1, s + i, used, combination, target) 
        used[i] = False
        combination.pop()
    
    return ret
        
used = [False] * 10
lst = sumCombinations(3, 0, used, [], 8)
print(lst)
# Output: [[1, 2, 5], [1, 3, 4], [1, 4, 3], [1, 5, 2], [2, 1, 5], [2, 5, 1], [3, 1, 4], [3, 4, 1], [4, 1, 3], [4, 3, 1], [5, 1, 2], [5, 2, 1]]