递归实现howManySort方法：计算非降序数组组合数

需求说明 #

实现howManySort(int length, int max)方法：

• length：目标数组的长度
• max：允许使用的最大数字（数字范围为1到max，包含两端）
• 返回值：由上述数字组成的、长度为length的非降序数组的组合总数
• 限制条件：仅允许用递归实现，禁止使用循环、数学公式，且不能返回或打印数组本身

示例 #

• 当length=3、max=2时，共4种组合：(1,1,1)、(1,1,2)、(1,2,2)、(2,2,2)
• 当length=2、max=3时，共6种组合：(1,1)、(1,2)、(1,3)、(2,2)、(2,3)、(3,3)

你尝试的代码（存在问题） #

public int howManySort(int length,int max){
 return howManySort(length,max,1);
}

// 私有方法缺失int i参数，编译无法通过
private int howManySort(int length,int max){
if(i>max){
 return 0;
}
if(length==0){
 return 1+howManySort(length,max,i+1);
}
return howManySort(length-1,max,i);
}

问题分析与修正方案 #

核心递归思路 #

我们需要一个带起始数字参数的辅助递归函数，定义为howManySortHelper(int length, int max, int start)，它的含义是：用从start到max的数字，组成长度为length的非降序数组的组合数。

递归逻辑拆分：

1. 终止条件1：如果length == 0，说明已经凑够了长度为length的数组，这是1种有效组合，返回1
2. 终止条件2：如果start > max，说明没有可选的数字了，无法组成有效数组，返回0
3. 递归分支：
   • 选择当前数字start：剩下的length-1个位置可以继续选start到max的数字（保证非降序），对应递归调用howManySortHelper(length-1, max, start)
   • 不选当前数字start：直接从start+1到max的数字中选length个，对应递归调用howManySortHelper(length, max, start+1)
   • 总组合数是这两个分支的结果之和

修正后的代码 #

public int howManySort(int length, int max) {
    // 从起始数字1开始递归
    return howManySortHelper(length, max, 1);
}

private int howManySortHelper(int length, int max, int start) {
    // 已经凑够数组长度，算1种组合
    if (length == 0) {
        return 1;
    }
    // 没有可选数字了，返回0
    if (start > max) {
        return 0;
    }
    // 选当前start的情况 + 不选当前start的情况
    return howManySortHelper(length - 1, max, start) + howManySortHelper(length, max, start + 1);
}

代码验证 #

以length=3、max=2为例：

• 调用howManySortHelper(3,2,1)：拆分为howManySortHelper(2,2,1) + howManySortHelper(3,2,2)
  • howManySortHelper(2,2,1)又拆分为howManySortHelper(1,2,1) + howManySortHelper(2,2,2)
    • howManySortHelper(1,2,1) = howManySortHelper(0,2,1) + howManySortHelper(1,2,2) = 1 + 1 = 2
    • howManySortHelper(2,2,2) = howManySortHelper(1,2,2) + howManySortHelper(2,2,3) = 1 + 0 = 1
    • 所以howManySortHelper(2,2,1) = 2+1=3
  • howManySortHelper(3,2,2) = howManySortHelper(2,2,2) + howManySortHelper(3,2,3) =1+0=1
• 总和3+1=4，和示例结果一致

内容的提问来源于stack exchange，提问作者Mohamad Masaada