java—计算3个目标总和的方法数

u4dcyp6a  于 2021-06-30  发布在  Java
关注(0)|答案(1)|浏览(271)

对于给定的 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;

}

0yycz8jy

0yycz8jy1#

您的方法有一些问题,即:

return counter++;

实际上应该是 return 1; 不能增加变量(例如。, a++ )否则,在递归调用期间,您将不会遍历所有可能的路径。在这里:

return numbers(a++, b, c, num) + numbers(a, b++, c, num);

你只有两条路,但实际上有三条,即:

return  numbers(a + 1, b, c, num) +
                numbers(a, b + 1, c, num) +
                numbers(a, b, c + 1, num);

然而,现在算法的问题是它将有重复的递归路径。因此,您可以调整方法以避免这种情况:

public static void numbers(int a, int b, int c, int num, Set<String> combinations){
    if (a + b + c <= num) {
        if (a + b + c == num) {
            combinations.add("(" + a + "," + b + "," + c + ")");
        } else {
            numbers(a + 1, b, c, num, combinations);
            numbers(a, b + 1, c, num, combinations);
            numbers(a, b, c + 1, num, combinations);
        }
    }
}

使用集合避免重复。
运行示例:

public class Main {
    public static void numbers(int a, int b, int c, int num, Set<String> combinations){
        if (a + b + c <= num) {
            if (a + b + c == num) {
                combinations.add("(" + a + "," + b + "," + c + ")");
            } else {
                numbers(a + 1, b, c, num, combinations);
                numbers(a, b + 1, c, num, combinations);
                numbers(a, b, c + 1, num, combinations);
            }
        }
    }

    public static void main(String[] args)
    {
        Set<String> combinations =  new LinkedHashSet<>();
        numbers(1, 1, 1, 5, combinations);
        combinations.forEach(System.out::println);
        System.out.println("Count : "+combinations.size());
    }
}

对于输入:

numbers(1, 1, 1, 5, combinations);

您将得到以下输出:

(3,1,1)
(2,2,1)
(2,1,2)
(1,3,1)
(1,2,2)
(1,1,3)
Count : 6

相关问题