Обратный путь решения всех возможных способов выбора винной бутылки

Question

Я только начал практиковать откат и проблемы с DP. Я проходил этот ответ на вопрос .Что касается проблемы выбора бутылки вина.Сначала я хотел написать код для печати всех возможных способов выбора винных бутылок.

Постановка задачи:
Представьте, что у вас есть коллекция из N вин, расположенных рядом друг с другом.полка.Для простоты давайте нумеруем вина слева направо, поскольку они стоят на полке с целыми числами от 1 до N соответственно.А для продажи вы можете выбрать либо слева, либо справа.Распечатать все возможные способы, бутылки вина можно продать?

Мой код указан ниже.

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);

        }                       
    }

Не работает.Он печатает результаты дважды.Кто-то может указать, что пошло не так?

И есть ли какие-либо предложения о том, как решить проблемы с DP?

Спасибо.

Answer 1

Если priceList достигает размера 1, выбор первой бутылки аналогичен выбору последней бутылки.Поэтому в этом случае следует выбирать только первую или последнюю бутылку.

Один из способов сделать это - выбрать последнюю бутылку, только если размер priceList больше 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);
        }
    }
}

Другими словами, когда вы выбираете n-1 бутылок, есть только один способ выбрать следующую (последнюю оставшуюся) бутылку.

Для входного списка [10, 20, 30,40, 50] выводит вывод:

[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]