algorithm - 可能なすべての有効な括弧を生成するためのこのアルゴリズムの時間計算量は?

Question

括弧の生成
n 対の括弧が与えられた場合、整形式の括弧のすべての組み合わせを生成する関数を作成します。

たとえば、n = 3 の場合、解セットは次のようになります。

"((()))"、"(()())"、"(())()"、"()(())"、"()()()"

---

個人的には、
時間の複雑さ
= O(n! ) (tmpStr をコピーする時間を含まない)、n は入力、
= O(n * n!) (tmpStr をコピーする時間を含む) だと思います。

スペースの複雑さ
= O(n) (スタック スペースの使用量)、
= O(n) (スタック + 再帰スペースの使用量)。

---

コード: Java

import java.util.List;
import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<String>();

        // Input checking.
        if (n <= 0) {
            list.add("");
            return list;
        }

        String tmpStr = "";
        for (int i = 0; i < n; i ++) tmpStr += "(";

        helper(n, tmpStr, 0, list);

        return list;
    }

    private void helper(int n, String tmpStr, int start, List<String> list) {
        // Base case.
        if (tmpStr.length() == 2 * n) {
            if (isValid(tmpStr)) list.add(tmpStr);
            return;
        }

        for (int i = start; i < tmpStr.length(); i ++) {
            // Have a try.
            tmpStr = tmpStr.substring(0, i + 1) + ")" + 
                     tmpStr.substring(i + 1, tmpStr.length());

            // Do recursion.
            helper(n, tmpStr, i + 1, list);

            // Roll back.
            tmpStr = tmpStr.substring(0, i + 1) + 
                     tmpStr.substring(i + 2, tmpStr.length());
        }
    }

    private boolean isValid(String str) {
        // Input checking.
        if (str == null || str.length() < 2) return false;

        Stack<Character> stack = new Stack<Character>();

        for (int i = 0; i < str.length(); i ++) {
            char curr = str.charAt(i);
            if (curr == '(') stack.push(curr);
            else {
                if (stack.isEmpty()) return false;
                stack.pop();
            }
        }

        if (stack.isEmpty()) return true;
        else return false;
    }
}