arrays - 返回可能组合数的递归函数

Question

我参加了面试，被问到一个问题，我想了解解决方案。

问题

创建一个递归函数，该函数返回给定长度数组的可能组合数，这些组合可以由非重复连续整数数组组成。

f(array, length) = 组合

例子1

• 数组 = [0,1,2,3]
• 长度 = 2
• 组合 = 10(所有组合:[0,0] [0,1] [0,2] [0,3] [1,1] [1,2] [1,3] [2,2] [2,3] [3,3])
• 请注意，[0,0] 是允许的，但 [1,0] 不是，因为 [0,1] 已定义

例子2

• 数组 = [0,1]
• 长度= 3
• 组合 = 4(所有组合:[0,0,0] [0,0,1] [0,1,1] [1,1,1])

提供了一个“提示”。面试官说数组本身应该无关紧要；长度是所需要的。

Answer 1

这个算法可以递归地表示，因为解决方案可以用较小输入的解决方案来表示。这里的“小”有两层意思:

• 数组的一个子集；具体是当前元素索引之后的子数组

• 更短长度的解决方案；这些可以加在一起得到长度 + 1 的解决方案

停止条件:

• 当数组大小A = 1时——只能生成一个组合

• 当长度L = 1 - 组合数=数组元素数

完全递归过程是一个非常简单的单行代码:

return [recursive call to rest of array, same length] + 
       [recursive call to same array, length - 1]

这称为动态规划。

代码:

int F(int A, int L)
{
    if (A <= 1) return 1;
    if (L <= 1) return A;
    return F(A - 1, L) + F(A, L - 1);
}

测试:

• F(4, 2) = 10
• F(2, 3) = 4
• F(3, 5) = 21(自己用笔和纸描出来看看)

---

编辑:我给出了一个优雅而简单的解决方案，但我可能没有像@RoryDaulton 那样解释清楚。也考虑给予他的回答信用。