面试题 08.09

Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n pairs of parentheses.

Note: The result set should not contain duplicated subsets.

For example, given n = 3, the result should be:

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

Solutions

• The same as problem 22, check for more solutions.

• dfs

class Solution {
public:
    vector<string> res;
    string path;
    void dfs(int n, int l, int r) {
        if (l == n && r == n) {
            res.push_back(path);
        }
        if (l < n) {
            path += '(';
            dfs(n, l + 1, r);
            path.pop_back();
        }
        if (r < l) {
            path += ')';
            dfs(n, l, r + 1);
            path.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        dfs(n, 0, 0);
        return res;
    }
};