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

Question

我接受了一次采访，被问到一个问题，我想了解解决方案。

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

f（数组，长度）=组合

• 数组=[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]

• 数组=[0,1]

提供了一个“提示”。采访者说阵列本身并不重要；长度就是所需要的。

Answer 1

你没有给出目标语言，也没有说你想要多少帮助。所以我将给出一个算法的总体想法，如果你知道某种语言的递归，那么这个算法应该很容易编码。问问你是否想要更多Python代码，我目前更喜欢的语言。

您知道需要进行递归，并且有两件事情可以进行递归：给定数组的长度或所需数组的长度。让我们在第二个循环，假设给定的数组是0，1，…，n-1，因为您知道实际内容是不相关的。

如果所需的长度r是1，您知道只有n所需的数组，即[0]、[1]、...，[n-1]。因此存在递归的基本情况。

如果您有长度r-1的“组合”，如何将其扩展为长度r并保持要求？看看长度r-1数组中的最后一个元素——让我们称其为k。下一个元素不能小于此，因此所有可能扩展到长度r的数组都是附加有k'，'k 1，...，n-1的r-1数组。这些是长度r的n-k数组。

是否清楚如何编码？请注意，您不需要保留所有长度为r-1的数组，您只需要计算以元素0或1或...n-1结尾的数组数量。这使得编码很方便——不需要太多内存。事实上，事情可以进一步减少——我将留给你。

请注意，面试官可能不想要代码，他希望你的思维过程引导代码看到你的思维方式。这是思考问题的一种方式。

Answer 2

该算法可以递归表示，因为解可以用较小输入的解来表示。这里的“较小”有两个含义：

>

数组的子集；特别是当前元素索引之后的子数组

较小长度的解决方案；这些可以加在一起得到长度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

编辑：我已经给出了一个优雅而简单的解决方案，但我可能没有像@RoryDaulton那样解释清楚。考虑也给他的答案加分。