Поиск подходящих пар скобок не работает?

Question

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

вопрос найти все комбинации допустимых п пар скобок

public class Foo{ 
    public void printCombinations(String prefix, int open, int close, int n){ 
     if (open > n) { 
      return; 
     } 
     if (close > n) { 
      return; 
     } 
     if (open == n && close == n){ 
      System.out.println(prefix); 
      return; 
     } 
     printCombinations(prefix + "(", open + 1, close, n); 
     printCombinations(prefix + ")", open, close + 1, n); 
    } 
    public static void main(String []args){ 
     HelloWorld w = new HelloWorld(); 
     w.printCombinations("", 0, 0, 3); 
    } 
} 

Когда я запускал эту программу, казалось, что распечатывал все комбинации, а не те, которые имеют действующие скобки. Я думал, что printCombinations(prefix + "(", open + 1, close, n); обеспечит, чтобы я сначала открывал скобу, а затем рекурсивно вызывал printCombinations(prefix + ")", open, close + 1, n);. Я вижу один результат с чем-то вроде )))(((. Как это возможно, если сначала добавить (?

Answer 1

это потому, что после того, как рекурсивные вызовы для printCombinations(prefix + "(", open + 1, close, n) закончены в стеке, ваш код начинает повторяться printCombinations(prefix + ")", open, close + 1, n). Именно поэтому вы получите один из строковых выводов, который начинается с ), а не из-за заказа, в который вы помещаете эти два рекурсивных вызова. Чтобы исправить это, вам необходимо условие, при котором close всегда меньше open. Как указано ниже,

public class Foo{ 
    public void printCombinations(String prefix, int open, int close, int n){ 
     if (open > n) { 
      return; 
     } 
     if (close > n) { 
      return; 
     } 
     if (open == n && close == n){ 
      System.out.println(prefix); 
      return; 
     } 
     printCombinations(prefix + "(", open + 1, close, n); 
     if (close < open) { 
      printCombinations(prefix + ")", open, close + 1, n); 
     } 
    } 
    public static void main(String []args){ 
     Foo w = new Foo(); 
     w.printCombinations("", 0, 0, 3); 
    } 
}