What is the time complexity of this algorithm to generate all possible valid parentheses?

Create parentheses . Given a pair of pairs of parentheses, write a function to create all combinations of well-formed parentheses.

For example, given n = 3, the solution set is:

() ()) "," (() ()) "," (()) () "," () (()) "," () () () "

---

Personally, I think time complexity
= O (n!) (Not including tmpStr copy time), n is input,
= O (n * n!) (Including tmpStr copy time).

space complexity
= O (n) (using stack space),
= O (n) (using stack space + recursion).

---

Code: 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;
    }
}