Time/Space Complexity of Generating Parentheses [Java]

Question

I am preparing a tutorial to solve the generating parentheses problem. (LeetCode #22) LeetCode mentions three different solutions but the third one looks confusing to me. I think that 3rd solution can be improved by dynamic programming. I wrote these two solutions but I am not sure about the time/space complexities. Could you please explain how we can find the complexities and compare two solutions? Thanks.

// Recursion
public static List<String> generateParentheses(int n) {
    List<String> list = new ArrayList<String>();

    if(n == 0){
        list.add("");
    }

    for(int k = 0; k < n; k++){
        for(String left : generateParentheses(k)){
            for(String inside : generateParentheses(n-k-1)){
                list.add(left + "(" + inside + ")");
            }
        }
    }

    return list;
}

// DP
public static List<String> generateParentheses(int n) {
    Map<Integer,List<String>> solutions = new HashMap<Integer,List<String>>();
    solutions.put(0, Arrays.asList(""));

    for(int k = 1; k <= n; k++){
        List<String> list = new ArrayList<String>();
        for(int i = 0; i < k; i++){
            for(String left : solutions.get(i)){
                for(String inside : solutions.get(k-i-1)){
                    list.add(left + "(" + inside + ")");
                }
            }
        }
        solutions.put(k, list);
    }

    return solutions.get(n);
}