Generate Parentheses

题目：

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

Example: Given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

分析：

既然candidate只有正反括号，拿就干脆不用for循环，只做两次不同的push_back()，这种情况下，退出条件要分析清楚，可以引入int count = 0，每次加入'('就做count++，表示还可以接受count个')'，反之则加入')'，然后count--。

解法：

class Solution {
public:
    /**
     * @param n n pairs
     * @return All combinations of well-formed parentheses
     */
    void dfs(string instance, vector<string>& res, int n, int count) {

        if (count < 0 || count > n) {
            return;
        }

        if (instance.size() == n * 2) {
            if (count == 0) {
                res.push_back(instance);
            }
            return;
        }

        instance.push_back('(');
        count++;
        dfs(instance, res, n, count);
        count--;
        instance.pop_back();

        instance.push_back(')');
        count--;
        dfs(instance, res, n, count);
        count++;
        instance.pop_back();

    } 

    vector<string> generateParenthesis(int n) {
        // Write your code here
        if (n <= 0) {
            return vector<string>();
        }

        string instance = "";
        vector<string> res;

        dfs(instance, res, n, 0);
        return res;
    }
};