题解 | #两个链表生成相加链表#

典型的回溯法！

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> ret;
    void backtrack(string& str, int left,int right, int n)
    {
        if (left > n || right > n || right > left) return;
        if(left == n && right == n)
        {
            ret.push_back(str);
            return;
        }
        str.push_back('(');
        backtrack(str, left+1, right, n);
        str.pop_back();
        str.push_back(')');
        backtrack(str, left, right + 1, n);
        str.pop_back();
    }
    vector<string> generateParenthesis(int n) {
        // write code here
        string str;
        backtrack(str, 0, 0, n);
        return ret;
    }
};