Возврат рекурсивной проблемы для решения сбалансированных скобок - PullRequest
Новая
       21

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

1 голос
/ 06 июня 2019

Мне нужно понять, как отказаться от рекурсивной функции. Я знаю, как это делается для основных функций, таких как факториал или Фибоначчи. Я не понимаю это для этой проблемы.

Я попытался устранить другие условия во втором рекурсивном вызове, но он генерирует все возможные наборы скобок, включая и несбалансированные. 

public final class Example {
    public static void parentheses(int left, int right, String str) {
        if (left == 0 && right == 0) {
            System.out.print(str);
            System.out.print(", ");
        }

        if (left > 0) {
            str += "(";
            parentheses(left - 1, right, str);
        }

        if (right > 0 && right > left) {
            str += ")";
            parentheses(left, right - 1, str);
        }
    }

    public static void main(String[] args) {
        parentheses(3, 3, "");
    }
}

Я хочу, чтобы результатом были все возможные наборы сбалансированных скобок. Однако после каждого рекурсивного вызова я получаю 1 дополнительную левую скобку. Ожидаемый результат:

((())), (() ()), (()) (), () (()), () () (),

Вывод, который я получаю:

((())), ((() ()), ((() () (), (() ()), (() (() (),

1 Ответ

0 голосов
/ 06 июня 2019

Проблема заключается в следующем. 

 str += "(";

вы каждый раз создаете новый строковый объект и передаете его в рекурсивном вызове.В результате каждый рекурсивный вызов имеет различное значение для строкового объекта, и, следовательно, ожидаемая рекурсия завершается ошибкой.Строки неизменны в Java.

Измените свой код ниже: 

        public static void parentheses(int left, int right, String str) {

        if ( right==0 && left==0) {
            System.out.print(str);
            System.out.print(", ");

        }
        if (left > 0) {
            parentheses(left-1, right, str +"(" ); // New object will be created but its value will be dereferenced from the old one and attached to the new one.
            // As a result all our manipulation of string we did will be saved.
        }
        if ( right >0 && right > left) {
            parentheses(left, right - 1, str +")" );
        }
    }

Ввод: 

parentheses(3,3,""); // Function call

Выход: 

((())), (()()), (())(), ()(()), ()()(),
...