22. Generate Parentheses

https://leetcode.com/problems/generate-parentheses/description/

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Thoughts

DFS:

生成n对所有可能的括号组合。让返回所有组合=>DFS，再配合验证是否合法的+1-1逻辑。

DP:

f[n]表示给定n时能形成的parentheses，它相当于是从partition拼接而来，也就是不同长度的j和i-j+1两个子结果拼在一起. 比如n = 3时, 相当于对n = 2时加个(), 那么把n = 2时可能组成的所有列出来,包括 n = 1 + 1时 把它们左边的外面加上()即可. f[0] = ""

f[1] = (f[0])

f[2] = (f[1]), (f[0])f[1]

f[3] = (f[0])f[2], (f[1])f[1], (f[2])

Code

/*
 * @lc app=leetcode id=22 lang=cpp
 *
 * [22] Generate Parentheses
 */

// @lc code=start
class Solution {
public:
    void dfs(int n, string &path, int sum, vector<string> &res) {
        if (n == 0) {
            if (sum == 0) {
                res.push_back(path);
            }
            return;
        } 
        path.push_back('(');
        dfs(n - 1, path, sum + 1, res);
        path.pop_back();
        if (sum > 0) {
            path.push_back(')');
            dfs(n - 1, path, sum - 1, res);
            path.pop_back();
        } 
    }

    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string path;
        dfs(n * 2, path, 0, res);
        return res;
    }
};
// @lc code=end

class Solution {    
    public List<String> generateParenthesis(int n) {
        List<List<String>> f = new ArrayList<>();
        f.add(Collections.singletonList(""));

        for (int i = 1; i <= n; i++) {
            List<String> list = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                for (String first : f.get(j)) {
                    for (String sec : f.get(i - 1 - j)) {
                        list.add("(" + first + ")" + sec);
                    }
                }
            }

            f.add(list);
        }

        return f.get(f.size() - 1);
    }
}

Analysis

时空复杂度(O(N^2)).