递归地将数字 4 的所有分区枚举为四个有序数字？

Question

可以将值 4 分配给长度为 4 的数组的所有情况的数量是：

[4,0,0,0]
[3,1,0,0]
[3,0,1,0]
[3,0,0,1]
[2,2,0,0]
[2,1,1,0]
...
[0,0,0,4]

如何用递归函数解决这个问题？

我以为用递归很容易解决，但是太难了

Answer 1

这是一种不同的看待方式。想象一下，你有一群 n 个人，他们必须分摊 $k 美元的账单。您如何列出这些人分摊账单的所有可能方式？

您可以使用的递归见解如下。看着第一个人，然后问——他们要付多少钱？如果他们支付 0 美元，则其余人必须共同支付 k 美元。如果他们支付 1 美元，剩下的人必须共同支付 1 美元。如果他们支付 2 美元，剩下的人必须共同支付 2 美元。更一般地说，如果他们支付 $d，则其余人必须共同支付 $k - d。因此，如果您有 n > 1 个人，请选择一个人（无论如何），然后对于他们可能支付的每笔金额，让他们支付该金额，其余人支付其余金额。

此过程的基本情况是只有一个人。如果只有一个人，剩下的账单是$k，那么他们必须支付所有$k 美元。别无选择。

在伪代码中，这可能看起来像这样：

SplitTheBill(n people, $k):
    if n == 1, output that the one person pays $k.
    else:
       pick one person p.
       for each amount $d between [=10=] and $k, inclusive:
           have person p pay $d.
           use SplitTheBill(n - 1 people, $k - $d) to list all ways
               the remaining people can pay the rest of the bill.

将此逻辑转化为代码需要您仔细考虑如何跟踪谁花了多少钱，以确定人员的正确顺序等。但希望这能让您了解如何解决这个问题。

祝你好运！

Answer 2

这是 JavaScript 中的示例，实现了 templatetypedef 共享的想法：

function f(n, k, i=1){
  if (i == n)
    return [k];
    
  const result = [];
    
  for (let s=0; s<=k; s++)
    f(n, k - s, i + 1).map(comb => result.push([s].concat(comb)));
  
  return result;
}

var n = 4;
var k = 4;

console.log(JSON.stringify(f(n, k)));

递归地将数字 4 的所有分区枚举为四个有序数字？

Recursively enumerating all partitions of the number 4 into four ordered numbers?

language-agnostic

algorithm

recursion