Sum of numbers using recursion java

Question

Let's say n = 4. With recursion I want to return:

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

Basically I want to take number n and with by combining numbers 1,2,3 and 4 create all possible variations when the number of sum == n.

This was my first idea, but it gives me

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

The main problem is that you are always recursing when sum != n. When the sum gets bigger than n, you never stop, hence the StackOverflowError This means we need to add a check and terminate when the sum gets bigger:

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);
    }
}

As a side-note, in your 2 last calls, you wrote 1 and 2 instead of 3 and 4, but that was probably just a typo.

Output from calling test_2("", 0, 4):

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

---

But do note that your current code is not very dynamic: it wouldn't work if you were to give values greater than 4 for n. I would suggest refactoring it a little.