fixing a recursive backtracking algorithm code

Question

i need to find an algorithm that use a recursive backtracking algorithm which will print me all the possible compositions to x1+x2+x3 to be equals to the number. lets say the input number is 4 so the method will print me 3 results:

1 1 2
1 2 1
1 1 2

...... The code:

public class getResult

 public static void results(int n)
    {
    int[] history= new int[3];
    results(n,history,0);
    }
    private static void results(int n,int[] history,int i)
    {
    if(n==0)
    {
    printHistory(history,0,i);
    System.out.println();
    }
    if`(n>0&&i<3)`
    {
    history[i]=1;

    //insert 1 to history in order to go back in case of wrong 
    // way using backtracking.
    results(n-1,history,i+1);//calling the function again, with n-1 , backup history, history[i+1]`
    history[i]=2;
    results(n-2,history,i+1);
        history[i]=3;
    results(n-3,history,i+1);
    //.....9
    }
    }
    private static void printHistory(int[] history,int from,int to)
    {
    if(from<to)
    {
    System.out.print(history[from]+"\t");
    printHistory(history,from+1,to);
    }
    }
    }

I have 2 questions: 1. how can I print only the results that concludes x1,x2,x3. Because for now, if i try to input num=5 it will print me the following results:

And i want to get the results that only conclude 3 numbers(without for example the results: 5, 4 1, 3 2, 2 3)..

2.Is there a way to write these lines better:

 history[i]=1;
results(n-1,history,i+1)`;`

instead every time to copy the code and subtract a number manually from the number?(The results should pass all over the numbers between 1 to 9)

Thank you all for help, if something isn't clear i would like to help :)

To print only 3 you can put n == 0 && i == 3 instead of n==0 where you print the result — Butiri Dan
– Butiri Dan, Commented May 24, 2019 at 12:56
@ButiriDan you are right! Thank you, and what about the other question? — Jordan_boy
– Jordan_boy, Commented May 24, 2019 at 12:58
I'm voting to close this question as off-topic because it's more suitable for codereview.stackexchange.com and I can't seem to pick it as a "Migrate..." reason — Shark
– Shark, Commented May 24, 2019 at 13:27
@ButiriDan But i am not allowed to use loop if i didn't mentioned. is there a way to write it with a recursion call? — Jordan_boy
– Jordan_boy, Commented May 24, 2019 at 13:29

Butiri Dan · Accepted Answer · 2019-05-24 13:15:04Z

0

For your second question you just have to extract the generic formula and use a loop

private static void results(int n, int[] history, int i) {
    if (n == 0 && i == 3) {
        printHistory(history, 0, i);
        System.out.println();
    }
    if (n > 0 && i < 3) {
        int LIMIT = 4;
        int step = 0;

        while (step < LIMIT) {
            history[i] = ++step;
            results(n - step, history, i + 1);
        }
    }
}

Result

answered May 24, 2019 at 13:15

Butiri Dan

1,7706 gold badges15 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Butiri Dan Over a year ago

Maybe this post will help you to replace that while Turning a recursive function into a for loop?

Collectives™ on Stack Overflow

fixing a recursive backtracking algorithm code

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related