java - 查找并打印 x1+x2+x3=num 的解数

Question

我需要编写一个recusive 函数来接收一个整数num并返回方程的解数:x1 + x2 + x3 = num , 其中x1,x2,x3是 1-10 之间的数字，该方法应打印所有解决方案。

例如如果num=3然后该方法将打印 1+1+1并将返回 1 .

如果num=5该方法将返回 6并将打印:

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

如果num<3或 num>30该方法将返回 0 .

该方法应该是递归的，不使用循环。不允许使用全局变量。列表也是不允许的。

这是我的代码，它工作正常但它也打印重复项，对于 num=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

这是我的代码:

public static void main(String[] args) {
    System.out.println("num of solutions: "+solutions(5));

}

public static int solutions(int num) 
{

    if (num < 3 || num > 30)
        return 0;

    return solutions(num, 1, 1, 1);
}
private static int solutions(int num, int x1, int x2, int x3)
{
    if (x1 < 1 || x1 > 10 || x2 < 1 || x2 > 10||x3 < 1 || x3 > 10)
        return 0;
    if (x1 + x2 + x3 > num)
        return 0;       
    if (x1 + x2 + x3 == num)
    {
        System.out.println(x1 + " + " + x2 + " + " + x3);
        return 1;
    }           
    return solutions(num, x1 + 1, x2, x3) + solutions(num, x1, x2 + 1, x3) + solutions(num, x1, x2, x3 + 1);

}

How do I get the desired output without duplicates?

Answer 1

你得到重复项的原因是 solutions(1,2,1) 和 solutions(2,1,1) 都会引导你到 2 + 2 + 1。

不重复三位数的简单方法是从 111 到 10、10、10，就好像它是十进制整数一样:

private static int solutions(int num, int x1, int x2, int x3)
{
  if (x1 > 10 || x1 > num)
    return 0;
  if (x2 > 10 || x1+x2 > num)
    return solutions(num, x1+1, 1, 1);
  if (x3 > 10 || x1+x2+x3 > num)
    return solutions(num, x1, x2+1, 1);

  int me = 0;
  if (x1+x2+x3 == num) {
    System.out.printf("%d + %d + %d\n", x1, x2, x3);
    me=1;
  }
  return me + solutions(num, x1, x2, x3+1);
}

这模仿了通过修剪搜索整个空间的方法，但更有效的解决方案可以只搜索 x1 和 x2 并设置 x3=num -x1-x2.