what this program prints the wrong reutls

Question

What I am trying to do is:

I have a list of values, and I want to list each three of them. For example:

I have:

"one", "two", "three", "four", "five"

And I want to print the following:

one two three
one two four
one four five
two three four
two three five
and so on

You got the point, I want every three values (not in order off course)

What I did is:

import java.util.*;

public class Solution {
    public static void main(String args[]) {
        String[] people = new String[] { "one", "two", "three", "four",
                "five" };
        Solution s = new Solution();
        s.solve(people, 3, new LinkedList<>(), 0);
    }

    public void solve(String[] people, int n, List<String> data, int i) {
        if (data.size() == n) {
            System.out.println(data.toString());

        } else if (i < people.length) {
            String value = people[i];
            solve(people, n, data, i + 1);
            data.add(value);
            solve(people, n, data, i + 1);
        }
    }
}

You can run it:

My problem is that it prints:

[five, four, five]

Which is obviously wrong, how can It print two same values? In my code, I add the value once and I don't add it another time

Could you help?

@PM77-1 I'm not asking how to do it, i'm asking about the bug in my code. — Paolo RLang, Sep 01 '17 at 18:16
@Paolo RLang Put a debug point at your print statement and test once. — Naman, Sep 01 '17 at 18:16
@nullpointer how come the value "five" comes twice? that's weird for me — Paolo RLang, Sep 01 '17 at 18:17
Learn to debug your code. Run it step-by-step and you will see. — PM 77-1, Sep 01 '17 at 18:42
See this lovely [debug](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) blog for help. — Prune, Sep 01 '17 at 21:47

score 0 · Answer 1 · answered Sep 01 '17 at 18:39

how can It print two same values?

The reason for that is the condition that you've put in your code:

else if (i < people.length)

To take you through the frames of execution:

solve(people, n, data, i + 1); 

// (1) this recurses until i = 4(which is less than the length=5)
// for the next iteration the condition i<people.length wouldn't be satisfied

// (2) hence this is called
data.add(value);  // data now has "five"

// since when the previous recursion ended i=4 (callee)
solve(people, n, data, i + 1); 
// (3) this recurses again and finds the same condition of not being able to recurse more
// hence data gets value = "four"

With i+1 it rotates back to (1) and prints "five" again.

PS: I would leave it to you to figure out, if what happens after that.

Hint: Execution doesn't end here. Hint++: Recursive Backtracking.

score 0 · Answer 2 · answered Sep 01 '17 at 19:21

public void solve(String[] people, int n, List<String> data, int i) {
    if (data.size() == n) {
        System.out.println(data.toString());
        return;
    }

    if (i == people.length) {
        return;
    }

    data.add(people[i]);
    solve(people, n, data, i + 1);
    data.remove(people[i]);
    solve(people, n, data, i + 1);
}

Output

[one, two, three]
[one, two, four]
[one, two, five]
[one, three, four]
[one, three, five]
[one, four, five]
[two, three, four]
[two, three, five]
[two, four, five]
[three, four, five]

what this program prints the wrong reutls

2 Answers2