2 проблемы о рекурсивной DFS

Question

/*
Problem 22 Generate Parentheses:
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.For example, given n = 3, a solution set is: "((()))", "(()())", "(())()", "()(())", "()()()"
 */

public List<String> generateParenthesis(int n) {
    List<String> list = new ArrayList<String>();
    backtrack(list, "", 0, 0, n);
    return list;
}

private void backtrack(List<String> list, String str, int open, int close, int max){

    if(str.length() == max*2){
        list.add(str);
        return;
    }
    if(open < max)
        backtrack(list, str + "(", open + 1, close, max);
    if(close < open)
        backtrack(list, str+")", open, close+1, max);
}

Это одно из популярных решений на LeetCode, я знаю теорию DFS, я просто не могу получить его за два очка.

1. В рекурсивной функции есть два параметра после добавления '(', либо добавить еще один '(' или добавить несколько ')', но код выполняется сверху вниз, как этот код может обрабатывать другие решения, кроме ((())) Как (() ()), как он добавляет ')' после двух '('

2. После завершения одного решения, добавьте его в список и верните, как оно получит другие решения после возврата? Разве это не означает, что этот метод закончится после возврата? Новый ученик о Java, спасибо за подробные ответы

Answer 1

Я вставил эту строку в верхней части вашего backtrack() метод:

System.out.println("backtrack(" + list + ", \"" + str + "\", " + 
                   open + ", " + close + ", " + max + ")");

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

backtrack([], "", 0, 0, 3)
-backtrack([], "(", 1, 0, 3)
--backtrack([], "((", 2, 0, 3)
---backtrack([], "(((", 3, 0, 3)
----backtrack([], "((()", 3, 1, 3)
-----backtrack([], "((())", 3, 2, 3)
------backtrack([], "((()))", 3, 3, 3)
---backtrack([((()))], "(()", 2, 1, 3)
----backtrack([((()))], "(()(", 3, 1, 3)
-----backtrack([((()))], "(()()", 3, 2, 3)
------backtrack([((()))], "(()())", 3, 3, 3)
----backtrack([((())), (()())], "(())", 2, 2, 3)
-----backtrack([((())), (()())], "(())(", 3, 2, 3)
------backtrack([((())), (()())], "(())()", 3, 3, 3)
--backtrack([((())), (()()), (())()], "()", 1, 1, 3)
---backtrack([((())), (()()), (())()], "()(", 2, 1, 3)
----backtrack([((())), (()()), (())()], "()((", 3, 1, 3)
-----backtrack([((())), (()()), (())()], "()(()", 3, 2, 3)
------backtrack([((())), (()()), (())()], "()(())", 3, 3, 3)
----backtrack([((())), (()()), (())(), ()(())], "()()", 2, 2, 3)
-----backtrack([((())), (()()), (())(), ()(())], "()()(", 3, 2, 3)
------backtrack([((())), (()()), (())(), ()(())], "()()()", 3, 3, 3)

Тире представляют глубину стека при каждом рекурсивном вызове (я достиг этого эффекта, добавив дополнительный String параметр для backtrack который инициализируется "" в generateParenthesis и объединяется знаком "-" каждый раз, когда происходит рекурсия).

Answer 2

Я думаю, что вы немного озадачены местоположением возврата, а также оператором if внутри вашей рекурсивной функции backtrack.

Рекурсивные функции идут все глубже и глубже, пока не достигают случая, называемого базовым случаем, из которого они не могут спуститься дальше. Вы должны заметить, что каждый уровень убывания достигается вызовом вашей рекурсивной функции. Важным моментом является то, что каждый вызов к нему является вызовом отдельной функции и, следовательно, должен возвращаться отдельно.

Если то, что вы интуитивно и, к сожалению, неправильно, хотя и было правильным, то при достижении базового варианта вы просто полностью прекратили бы рекурсию. Вместо этого, если у вас есть рекуррентное отношение, как показано ниже, и вы делаете вызов, такой как f(n), из функции g, ваша рекуррентность будет уменьшаться как f(n-1), f(n-2),...f(2), f(1), f(0). Когда f (0) вернется, он не вернет свое значение g. Фактически, он снова вернет свое значение функции f, аргумент которой был равен 1. (то есть, в основном, следуя направлению, которое он использовал при понижении до f(0), только в обратном порядке) f(1) вернется к функция f, аргумент для которой был 2. Это будет продолжаться до тех пор, пока вы не достигнете вызова аргумента f, для которого было n. Только тогда возвращаемое значение будет возвращено g.

private void f(int i){
    if(i == 0) {
        return 0;
    }
    else {
        return f(i-1); 
    }
}

Первый вопрос, который вы имеете в виду, я думаю, что вам будет проще ответить, если вы получите то, что я упомянул выше. То, что я упомянул выше, было в двух словах, что вызов низшего уровня рекурсии не влечет за собой тот факт, что как только этот вызов нижнего уровня вернется, текущий уровень рекурсии также будет прерван. Если вы понимаете этот факт, чтобы ответить на ваш первый вопрос, все, что вам нужно сделать, это заметить, что ветвление в функции возврата осуществляется с использованием двух функций if, а не одной функции if&else-if. По сути, как только первый (т. Е. Вызов с возвратом '(' в качестве аргумента) на нижний уровень рекурсии вернется, поскольку текущий уровень рекурсии не завершится, будет выполнена отдельная проверка, если будет найдена необходимость (т.е. close