找到有效的括号对不起作用？

Question

我做的编码问题不看答案，我在努力寻找有什么错我的思维过程

的问题是要找到支架的有效N对所有组合

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