Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is:
[           
  "((()))",          
  "(()())",            
  "(())()",           
  "()(())",            
  "()()()"            
]

只要确定了 ( 的位置， ) 也确定了。
可以用回朔法，状态为 ( 在结果中的位置，例如 n = 4 时，某一个状态为013，意味着目前已经确定的某个结果为 ((#(####
解空间：

class Solution {
public:
    typedef vector<string> Ans;
    vector<string> generateParenthesis(int n) {
        if (n == 0) return {""};
        if (n == 1) return {"()"};
        Ans ans;
        string res(n * 2, ' ');
        res[0] = '(';
        res[n * 2 - 1] = ')';
        search(1, n, 1, res, ans);
        return ans;
    }
    void search(int count, int n, int cur, string& res, Ans& ans) {
        if (++count == n) {
            for (int i = cur; i < 2 * n - 1; i++) {
                string newres(res);
                newres[i] = '(';
                for (int j = 1; j < 2 * n - 1; j++) {
                    if (newres[j] == ' ') {
                        newres[j] = ')';
                    }
                }
                ans.push_back(newres);
            }
        } else {
            for (int i = cur; i < 2 * count - 1; i++) {
                string newres(res);
                newres[i] = '(';
                search(count, n, i + 1, newres, ans);
            }
        }
    }
};

FEATURED TAGS

FRIENDS