algorithm - 从 1 到 k 中选择数字使其总和等于 n 的方法有多少？

Question

问题如下：给定 n (1->1000) 和 k(1->100)，找出从 1 到 k 中选取数字的可能方法数，使它们的总和等于 n。

这是一个例子：

n = 5; k = 3;

可能的方式：

1*3 + 1*2 = 5

1*3 + 2*1 = 5

1*2 + 3*1 = 5

2*2 + 1*1 = 5

5*1 = 5

==> 我们有 5 种可能的方法

我尝试过组合，写下许多示例以找到通用解决方案，但没有运气。

请帮我解决这个问题，谢谢！

标签： algorithm

Answer 1

您描述的问题称为分区。它需要重复才能得到解决方案。我从这个问题中调整了我的解决方案，其中包含对这个想法的详细解释。请小心，因为这个数字增长得非常快，例如对于 n = 100 和 k = 6，您将得到 189509 个可能的总和。这是 C++ 中的代码：

#include <string>
#include <algorithm>

int nrOfSums = 0;
void partition(int n, int max, std::string prefix) {
    if (n == 0) {
        std::cout<<prefix<<std::endl;
        nrOfSums++;
        return;
    }

    for (int i = std::min(max, n); i >= 1; i--) {
        partition(n - i, i, prefix + " " + std::to_string(i));
    }
}
void partition(int n, int k) {
    partition(n, k, "");
}


int main()
{
    int n = 8, k = 3;
    partition(n, k);
    std::cout << "number of possible sums: "<< nrOfSums;
}

n = 8, k = 3 的输出：

 3 3 2
 3 3 1 1
 3 2 2 1
 3 2 1 1 1
 3 1 1 1 1 1
 2 2 2 2
 2 2 2 1 1
 2 2 1 1 1 1
 2 1 1 1 1 1 1
 1 1 1 1 1 1 1 1
number of possible sums: 10