Help with writing this recursion backtracking algorithm

[rian bron]

Hello guys, i am stuck a few days already on my problem my school gave me:
The question is :
"Write a recursive method without using any loops, that will  count all the number of possible compositions of x1+x2+x3=num."
i tried to do it with the following code:

public static void solutions(int n)
        {
         int[] history= new int[3];
         solutions(n,history,0);
        }
        private static void  solutions(int n, int[] history,int i)
        {
         if(n==0)
         {
         printHistory(history,0,i);
         System.out.println();
        }
         if(n>0&&i<3)
         {
         history[i]=1;
         solutions(n-1,history,i+1);
         history[i]=2;
         solutions(n-2,history,i+1);
         history[i]=3;
         solutions(n-3,history,i+1);
         history[i]=4;
         solutions(n-4,history,i+1);
         history[i]=5;
         solutions(n-5,history,i+1);
          history[i]=6;
         solutions(n-6,history,i+1);
          history[i]=7;
         solutions(n-7,history,i+1);
          history[i]=8;
         solutions(n-8,history,i+1);
          history[i]=9;
         solutions(n-9,history,i+1);
         }
        }       
        private static void printHistory(int[] history,int from,int to)
        {
         if(from<to)
         {
         if(history.length>=3)
         {
         System.out.print(history[from]+"+");
         printHistory(history,from+1,to);
        }
        }
        }

I have 2 problems:
1.The method needs to return  an int that represents the number of results possible, but of some reason the returned is always 1, why is that?

2. lines 15-32 makes the code really go longer than it should, is there a  way to get all over the number 1-9 with a recursion call instead of copying it over and over again?
Thank you Very much!

[salvin francis]

Are negative numbers allowed ?
Then I think there could be infinite possibilities.

Instead of trying to solve this directly in Java code, can you work it out in plain english, how would you manually solve this problem.
e.g. Lets take num=5
what are the possibilities of x1, x2, x3 that add up to 5 and how did you come up with that ?

[salvin francis]

rian bron wrote:... 1-9 with a recursion call instead of copying it ...

Why is 0 not considered ?
e.g. if num=5, then 0+0+5 =5

Are there any other restrictions on the value of x1, x2, x3 ?

[rian bron]

salvin francis wrote:Are negative numbers allowed ?
Then I think there could be infinite possibilities.

Instead of trying to solve this directly in Java code, can you work it out in plain english, how would you manually solve this problem.
e.g. Lets take num=5
what are the possibilities of x1, x2, x3 that add up to 5 and how did you come up with that ?

Sorry i forgot to mentioned that negative numbers are not allowed,
and I tried to do what you said, and this is the result i got into.
The main problem is that the returned int is always staying 1 and does not represent the real answer.
It is probably because i don't insert the counting in the correct place, but i tried few places and still didn't get it right.
Can you help me with that?

[rian bron]

salvin francis wrote:

rian bron wrote:... 1-9 with a recursion call instead of copying it ...

Why is 0 not considered ?
e.g. if num=5, then 0+0+5 =5

Are there any other restrictions on the value of x1, x2, x3 ?

Yes the number must me between 1 to 9 (x>=1&&x<=9)

[salvin francis]

rian bron wrote:...Yes the number must me between 1 to 9 (x>=1&&x<=9)

Great, Now that we know that, I hope there are no other restrictions such as repeating values for x1,x2,x3.
As I asked before, can you work out in plain english and not in java code, how you would solve this problem ?

[rian bron]

salvin francis wrote:

rian bron wrote:...Yes the number must me between 1 to 9 (x>=1&&x<=9)

Great, Now that we know that, I hope there are no other restrictions such as repeating values for x1,x2,x3.
As I asked before, can you work out in plain english and not in java code, how you would solve this problem ?

Lets say i am working right now on X,  so as a start x,y,z=1.
and i will add up 1 each round until x will be equals to 10, when this will happen I will set x=1 and start add up 1 to y each round until y=10. when this will happen i will set y=1 and add up 1 each round to z.
when z will be equals to 10, i will return the counting variable?


Is this method is correct?

[salvin francis]

I am unsure why you are counting till 10, but here's my approach:

First of all, we need to validate num. Since you are allowing x1,x2,x3 to be a min of 1 and a max of 9, num can only lie between 3 and 27.

The simplest brute force to check a number (say 5) would be to loop between 1 to 3. (i.e. 1 till num-2)

Table for x1 = 1: x1 x2 x3 Sum 1 1 1 3 1 1 2 4 1 1 3 5 <-- Found a match 1 2 1 4 1 2 2 5 <-- Found a match 1 2 3 6 1 3 1 5 <-- Found a match 1 3 2 6 1 3 3 7


Do you see a pattern emerging above ?

[rian bron]

salvin francis wrote:I am unsure why you are counting till 10, but here's my approach:

First of all, we need to validate num. Since you are allowing x1,x2,x3 to be a min of 1 and a max of 9, num can only lie between 3 and 27.

The simplest brute force to check a number (say 5) would be to loop between 1 to 3. (i.e. 1 till num-2)

Table for x1 = 1: x1 x2 x3 Sum 1 1 1 3 1 1 2 4 1 1 3 5 <-- Found a match 1 2 1 4 1 2 2 5 <-- Found a match 1 2 3 6 1 3 1 5 <-- Found a match 1 3 2 6 1 3 3 7


Do you see a pattern emerging above ?

you are basically right, but the thing is the i need to get all the possible compositions for the number.
for example if you chose 5, i need to get 6 as an answer:
1 1 3
1 2 2
1 3 1
2 1 2
2 2 1
3 1 1
It doesn't only need to find the possible compositions from left to right, it needs to find all compositions from right to left too.
But my problem is with the returning int, i get a wrong int every time i run this method, i get 1 every time instead of the correct number of results possible.
can you help me with that?

[salvin francis]

The example I showed you for only for x2,x3 for x1=1. It gets 3 matches. Similarly you can loop for x1=2,3,etc..

Lets forget recursion, can you implement this using a simple for loop ?

[rian bron]

salvin francis wrote:The example I showed you for only for x2,x3 for x1=1. It gets 3 matches. Similarly you can loop for x1=2,3,etc..

Lets forget recursion, can you implement this using a simple for loop ?

yes, i would do it like this:

int count=0;
for(x=1;x<=9;x++)
       for(y=1;y<=9;y++)
       for(z=1;z<=9;z++)
       if(x+y+z==n)
       count++;

[rian bron]

salvin francis wrote:The example I showed you for only for x2,x3 for x1=1. It gets 3 matches. Similarly you can loop for x1=2,3,etc..

Lets forget recursion, can you implement this using a simple for loop ?

Ok! i figured it out how to write the same method with recursion, but i now have my last problem, the method i wrote gives me all the results compositions possible , but the method does not stop running, i think it is  a problem with the base case but i don't know what:

if(x+y+z==n)
        {
            System.out.println(x+" "+y+" "+z);
            count++;
        }
        if(x<9)
        {
            getR(n,x+1,y,z,count);
            if(y<9)
            {
                x=1;
                getR(n,x,y+1,z,count);   
                if(z<9)
                {
                    y=1;
                    getR(n,x,y,z+1,count);
                }
            }
          
        }

        return count;

Do you know what is the problem?

[salvin francis]

instead of using if, use else-if since your cases are exclusive. I think there is some more problems with the counts anyways.
When using recursion, I think its best to print all variables to see what is happening in each call.

[rian bron]

salvin francis wrote:instead of using if, use else-if since your cases are exclusive. I think there is some more problems with the counts anyways.
When using recursion, I think its best to print all variables to see what is happening in each call.

you are right, but my task is to print the number of results there are , for example for num=4, i need to get 3 because there are 3 results possible: 1 1 2, 1 2 1 , 2 1 1

[salvin francis]

I understand what you need, here's your code with a little modification from my end:

	public int getR(int n, int x, int y, int z, int count) {
		//-- TODO: validate that x,y,z are >0
		if (x + y + z == n) {
			System.out.println("Match: " + x + " " + y + " " + z);
			count++;
		}
		int maxBounds = Math.min(n - 2, 9);
		if (x < maxBounds) {
			count = getR(n, x + 1, y, z, count);
		}
		else if (y < maxBounds) {
			count = getR(n, 1, y + 1, z, count);
		}
		else if (z < maxBounds) {
			count = getR(n, 1, 1, z + 1, count);
		}

		return count;
	}

[salvin francis]

maxBounds = Math.min(n - 2, 9);

This ensures that for smaller numbers, the method does not iterate through unnecessary values. Like I mentioned before, your code simply needed an if-else instead of just a if statement.