Leetcode 22: 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:
"((()))", "(()())", "(())()", "()(())", "()()()"

本题要求产生所有括号对，对于这种遍历所有可能性的题目，可以用DFS来遍历，使用DFS，构建树一共有几层，每一层有多少个branches. 这个题目中，一共是有N*2层，即括号的位置数，每一个位置都可以有（ 和） 两种可能，对于（，只有在（ 数目 < n时加入到结果中，对于 )，只有在）数目< n时加入才是valid的。

class Solution {
private:
    void DFS(int n, string solu, vector<string> &rst, int left, int right) {
        //base case
        if (left + right == n * 2) {
            rst.push_back(solu);
            return;
        }
        //two branch: add ( / add )
        if (left < n) {
            solu += '(';
            DFS(n, solu, rst, left+1, right);
            solu.resize(solu.size()-1);
        }
        if (left > right) {
            solu += ')';
            DFS(n, solu, rst, left, right+1);
            solu.resize(solu.size()-1);
        }
    }
public:
//use dfs solution
    vector<string> generateParenthesis(int n) {
        vector<string> rst;
        //sanity check
        if (n == 0) return rst;
        string solu = "";
        DFS(n, solu, rst, 0, 0);
        return rst;
    }
};