使用递归java的数字总和

Question

让我们说吧n = 4.随着递归,我想返回:

1 1 1 1
1 1 2
1 3
2 1 1
2 2
3 1
4

基本上我想取数字n,并通过组合数字1,2,3和4创建所有可能的变化时的数量sum == n.

这是我的第一个想法,但它给了我

线程"main"java.lang.StackOverflowError中的异常

public static void test_2(String path, int sum, int n){
    if(sum == n){
        System.out.println(path);
    } else {
        test_2(path+"1 ", sum + 1, n);
        test_2(path+"2 ", sum + 2, n);
        test_2(path+"3 ", sum + 1, n);
        test_2(path+"4 ", sum + 2, n);
    }
}

Answer 1

主要问题是你总是在递归时sum != n.当总和大于时n,你永远不会停止,因此StackOverflowError这意味着我们需要添加一个检查并在总和变大时终止:

public static void test_2(String path, int sum, int n) {
    if (sum == n) {
        System.out.println(path);
    } else if (sum < n) { // <-- only recurse if the sum is less than the target
        test_2(path+"1 ", sum + 1, n);
        test_2(path+"2 ", sum + 2, n);
        test_2(path+"3 ", sum + 3, n);
        test_2(path+"4 ", sum + 4, n);
    }
}

作为旁注,在你的最后2个电话中,你写了1和2而不是3和4,但这可能只是一个错字.

来电的输出test_2("", 0, 4):

1 1 1 1 
1 1 2 
1 2 1 
1 3 
2 1 1 
2 2 
3 1 
4 

但请注意,您当前的代码不是非常动态:如果要为大于4的值提供值,则无效n.我建议稍微重构一下.