对于给定的 num=4
,以及变量 a
, b
, c
,它们的值可以从 1 to 10
. 我想计算一下有多少种方法可以将这3个变量相加得到值 num
. 例如,例如 num=4
```
1+1+2, 2+1+1, 1+2+1
有三种方法
我试图用递归来解决这个问题。也许我错过了什么大事,我会接受你的建议!
// we can assume the values are positive
// we can assume the num is geater than 4
public static int numbers(int a, int b, int c, int num) {
Integer counter = 0;
if (a + b + c > num) {
return 0;
}
// if we reached a variation of num we add to counter
if (a + b + c == num) {
return counter++;
}
// if we didnt reach a variation of 0
// we do recurion to a+1 then recurion where we add to b and c
if (a + b + c < num && a < num - 1 && b < num - 1 && c < num - 1) {
return numbers(a++, b, c, num) + numbers(a, b++, c, num);
}
// we add to c if its not equal to a so we dont get double
if (a + b + c < num && a < c) {
return numbers(a, b, c++, num);
}
return counter;
}
1条答案
按热度按时间0yycz8jy1#
您的方法有一些问题,即:
实际上应该是
return 1;
不能增加变量(例如。,a++
)否则,在递归调用期间,您将不会遍历所有可能的路径。在这里:你只有两条路,但实际上有三条,即:
然而,现在算法的问题是它将有重复的递归路径。因此,您可以调整方法以避免这种情况:
使用集合避免重复。
运行示例:
对于输入:
您将得到以下输出: