java - 递归地查找三个数字的总和为给定数字的组合

Question

给定 1 到 30 之间的数字，查找总和等于该数字的所有三数组合，并在不使用循环的情况下返回组合的数量。例如，给定 5，打印

1 + 1 + 3 
1 + 2 + 2 
1 + 3 + 1 
2 + 1 + 2 
2 + 2 + 1 
3 + 1 + 1

这就是我现在所拥有的，使用 Java。

private static int numbers(int num, int num1, int num2, int num3){
    boolean valid_solution = num1+num2+num3 == num;
    int counter = 0;
    if (valid_solution){
      System.out.println(num1+" + "+num2+" + "+num3);
      counter++;
    }
    if (num1>10 || num2>10 || num3>10 || num1+num2+num3>num){
      return counter;
    }
    counter += numbers(num, num1 + 1, num2, num3)+numbers(num, num1, num2 + 1, num3)+numbers(num, num1, num2, num3 + 1);
    return counter;
  }

  public static int solutions(int num){
    if (num < 0 || num > 30) return 0;
    return numbers(num, 1, 1, 1);
  }

我似乎得到了重复项，例如 5-

3 + 1 + 1
2 + 2 + 1
2 + 1 + 2
2 + 2 + 1
1 + 3 + 1
1 + 2 + 2
2 + 1 + 2
1 + 2 + 2
1 + 1 + 3

编辑 - 我也不允许使用全局变量。

Answer 1

如果添加一点日志记录，您就会明白为什么会发生重复

1:1:1
2:1:1
3:1:1
3 + 1 + 1
4:1:1
3:2:1
3:1:2
2:2:1
2 + 2 + 1
3:2:1
2:3:1
2:2:2
2:1:2
2 + 1 + 2
3:1:2
2:2:2
2:1:3
1:2:1
2:2:1
2 + 2 + 1
3:2:1
2:3:1
2:2:2
1:3:1
1 + 3 + 1
2:3:1
1:4:1
1:3:2
1:2:2
1 + 2 + 2
2:2:2
1:3:2
1:2:3
1:1:2
2:1:2
2 + 1 + 2
3:1:2
2:2:2
2:1:3
1:2:2
1 + 2 + 2
2:2:2
1:3:2
1:2:3
1:1:3
1 + 1 + 3
2:1:3
1:2:3
1:1:4
counter:9

因此，由于您对递增的数字进行递归调用，因此当您递归调用 num2+1 时，您需要确保 num1 小于或等于 num2 以避免重复