Sum of numbers using recursive java

Question

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 the number n and using a combination of numbers 1,2,3 and 4 to create all the possible options when the number sum == n .

It 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 always return sum != n When the amount becomes greater than n , you never stop, therefore, StackOverflowError This means that we need to add a check and complete when the amount becomes larger:

 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 last two calls, you wrote 1 and 2 instead of 3 and 4, but that was probably just a typo.

The output of the call 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 note that your current code is not very dynamic: it will not work if you give values ​​greater than 4 for n . I would suggest a bit of refactoring.