java - 生成所有有效的括号

我想创建给定输入数字n的所有有效括号字符串。例如，如果n = 3，则输出应如下所示：

["((()))","(()())","(())()","()(())","()()()"]

我针对此问题的代码如下：

private void allParenthesis(List<String> result, int n){
    if(n == 1){
        result.add("()");
        return;
    }
    allParenthesis(result, n-1);

    List<String> newResult = new ArrayList<String>();
    for(String str : result){
        newResult.add("("+str+")");
        newResult.add("()"+str);
        newResult.add(str+"()");
    }
    System.out.println(newResult+" for n:"+n);
    result = new ArrayList<String>(newResult);

}

我在以下功能中使用此功能，

public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<String>();

    allParenthesis(result,n);
    return result;
}

但是当我输入n = 3时，我得到以下输出，

["()"]

我要去哪里错了？我是否错过任何简单的事情？

最佳答案

您将丢失所创建的结果，并且不会将其传递给递归。我已经修复它并简化为一个功能。同样使用数组列表将意味着有重复项。例如。

Str = "()";
newResult.add("()"+str); //this will result in ()()
newResult.add(str+"()"); //this will also result in the same

如果需要以上结果，请继续使用arraylist。如果不是，我建议使用LinkedHashSet作为设置，不要重复和链接一次，以便保持插入顺序。如果您不关心结果的顺序，则可以使用HashSet。

我同时提供了ArrayList和LinkedHashSet版本。

HashSet-无复制

private LinkedHashSet<String> generateParenthesis(int n){
    if(n == 1){
        LinkedHashSet<String> result = new LinkedHashSet<String>();
        result.add("()");
        return result;
    }
    LinkedHashSet<String> result = generateParenthesis(n-1);

    LinkedHashSet<String> newResult = new LinkedHashSet<String>();
    for(String str : result){
        newResult.add("("+str+")");
        newResult.add("()"+str);
        newResult.add(str+"()");
    }
    result.addAll(newResult);
    return result;
}

ArrayList-保持低调

private ArrayList<String> generateParenthesis(int n){
    if(n == 1){
        ArrayList<String> result = new ArrayList<String>();
        result.add("()");
        return result;
    }
    ArrayList<String> result = generateParenthesis(n-1);

    ArrayList<String> newResult = new ArrayList<String>();
    for(String str : result){
        newResult.add("("+str+")");
        newResult.add("()"+str);
        newResult.add(str+"()");
    }
    result.addAll(newResult);
    return result;
}

您可以像这样使用此功能。

LinkedHashSet<String> result = generateParenthesis(3);
System.out.println(result);

关于java - 生成所有有效的括号，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53292852/