Backtracking solution of all possible ways of choosing wine bottle

Question

I just started practicing backtracking and DP related problems.I was going through this quora answer. With respect to the wine bottle selecting problem. I first wanted to write a code to print all possible ways of selecting the wine bottles.

Problem statement :
Imagine you have a collection of N wines placed next to each other on a shelf. For simplicity, let's number the wines from left to right as they are standing on the shelf with integers from 1 to N, respectively. And for selling you can choose either the one on the left or the one on the right. Print all possible ways, the wine bottles can be sold ?

My code is below.

public static void backtrackWineAll(List<Integer> priceList, List<Integer> choosen) {

        if(priceList.isEmpty()) {
            System.out.println(choosen);
        }
        else {

            Integer first = priceList.remove(0);
            choosen.add(first);//choose the first bottle.

            backtrackWineAll(priceList, choosen);

            choosen.remove(choosen.size()-1);
            priceList.add(0, first);


            int lastPos = priceList.size()-1;
            Integer last = priceList.remove(lastPos);
            choosen.add(last); //choose the last bottle.

            backtrackWineAll(priceList, choosen);

            choosen.remove(choosen.size()-1);
            priceList.add(last);

        }                       
    }

It is not working. It is printing the results twice. can someone point out what went wrong?

And any suggestion on how to approach DP problems?

Thanks.

Answer 1

If priceList reaches a size of 1, selecting the first bottle is the same as selecting the last bottle. Therefore you should only select either the first or the last bottle in this case.

One way to do it is to only select the last bottle if the size of priceList is larger than 1:

public static void backtrackWineAll(List<Integer> priceList, List<Integer> choosen) {

    if(priceList.isEmpty()) {
        System.out.println(choosen);
    } else {
        Integer first = priceList.remove(0);
        choosen.add(first);//choose the first bottle.

        backtrackWineAll(priceList, choosen);

        choosen.remove(choosen.size()-1);
        priceList.add(0, first);

        if (priceList.size () > 1) { // the added condition
            int lastPos = priceList.size()-1;
            Integer last = priceList.remove(lastPos);
            choosen.add(last); //choose the last bottle.

            backtrackWineAll(priceList, choosen);

            choosen.remove(choosen.size()-1);
            priceList.add(last);
        }
    }
}

In other words, once you choose n-1 bottles, there is only one way to choose the next (final remaining) bottle.

For an input List of [10, 20, 30, 40, 50] it prints the output:

[10, 20, 30, 40, 50]
[10, 20, 30, 50, 40]
[10, 20, 50, 30, 40]
[10, 20, 50, 40, 30]
[10, 50, 20, 30, 40]
[10, 50, 20, 40, 30]
[10, 50, 40, 20, 30]
[10, 50, 40, 30, 20]
[50, 10, 20, 30, 40]
[50, 10, 20, 40, 30]
[50, 10, 40, 20, 30]
[50, 10, 40, 30, 20]
[50, 40, 10, 20, 30]
[50, 40, 10, 30, 20]
[50, 40, 30, 10, 20]
[50, 40, 30, 20, 10]