java - 使用递归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 的数字时。

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

Exception in thread "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 

---

但请注意，您当前的代码不是很动态:如果您为 n 提供大于 4 的值，它将无法工作。我建议稍微重构一下。