具有唯一解决方案的递归问题

Question

出于好奇，我编写了一个程序，计算产生一定分数的滑雪球角色的不同组合数量。孔的值[0,10,20,30,50100]保持为枚举值。还有九个滚珠。我将每个滚动处理为递归调用下一个滚动，同时循环遍历每个滚动的值：

private static void scoreCalc(int targetScore, int score, int ballNumber)
{
    for(SkiBallHoles hole : SkiBallHoles.values())
    {
        score += hole.getValue();
        ballNumber--;
        if (ballNumber > 0) {
            scoreCalc(targetScore, score, ballNumber);
        }
        if (ballNumber == 0 && score == targetScore) {
            frequency++;
        }
        ballNumber++;
        score -= hole.getValue();
    }
}

分数本身从主函数中的for循环输入到该函数，形成一系列设置函数：

while(score <= 900){
    writer.println(calculateFrequency(score));
    score += 10;
}
private static String calculateFrequency(int targetScore)
{
    frequency = 0;
    scoreCalc(targetScore);
    return targetScore + ": " + frequency;
}
private static void scoreCalc(int targetScore)
{
     scoreCalc(targetScore, 0, BALLCOUNT);
}

---

这种方法的问题在于，它不计算唯一解决方案的数量。即0 0 0 0 00 0 0 0 10被计数为不同于10 0 0 0，而它们实际上是产生分数的值的相同组合。

如何修改我的方法以只计算唯一的解决方案？

感谢=）

Answer 1

通过按值对孔进行排序，您只能在已排序的解决方案（0 0 0 0 0 0 0 0 10、0 0 0 0 0 0 0 10 20等）上迭代。

您的解决方案是否在相同孔的不同排列上迭代？（即对0 0迭代两次）如果是这样，您可以将结果除以n！。然而，这种方法会更慢。

Answer 2

谢谢@omer681，你给我指明了正确的方向。

我的修复方法涉及将数组中的Hole值从enums更改为int。然后，在递归中，在for循环开始的地方传递一个"itter"int。在递归中，这个数字是从for循环中继承的。这样，for循环中的每个步骤都会限制下面循环中的步骤数。这适用于任何数量的球和得分洞。

    private static void scoreCalc(int targetScore, int score, int ballNumber,
    int itter)
{
    for(int i = itter; i < HOLEVALUES.length; i++)
    {
     ...
     if (ballNumber > 0) {
         scoreCalc(targetScore, score, ballNumber, i);
     ...
    }
}
private static void scoreCalc(int targetScore)
{
    scoreCalc(targetScore, 0, BALLCOUNT, 0);
}