首页 > 代码库 > [LeetCode] 22. Generate Parentheses

[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:

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

解法: backtracking + 递归, 直接套用backtracking的模板解法.
 1 class Solution { 2 public: 3     vector<string> generateParenthesis(int n) { 4         vector<string> allsol; 5         string sol; 6          7         gp(n, 0, 0, sol, allsol); 8         return allsol; 9     }10     11     void gp(int n, int nleft, int nright, string& sol, vector<string>& allsol) {12        if (nleft == n && nright == n){13            allsol.push_back(sol);14            return;15        }16        17        if (nleft < n){18            sol.push_back(();19            gp(n, nleft+1, nright,sol, allsol);20            sol.pop_back();21        }22        23        if (nleft > nright){24            sol.push_back());25            gp(n, nleft, nright+1, sol,allsol);26            sol.pop_back();27        }28        29        return;30     }31 };

 

[LeetCode] 22. Generate Parentheses