22. Generate Parentheses
Description
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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
Analysis
本题要求给出n对括号所组成的所有的well-formed的可能的括号排列。其实就是求让n对括号相互匹配的全排列。
很明显这种求全排列的题目肯定要利用回溯法，但是如何定义well-formed呢？即如何从n对括号的全排列中删除掉不符合题目要求的情况呢？这里提供一个思路:
每次递归时记录左右括号的数量，放置括号时，面临两种选择，要么放左括号要么放右括号;要求是，右括号不能比左括号少，左右括号数目都大于0，左右括号数目之和不能超过2*n。
算法的复杂度是O(结果的数量)，因为卡特兰数并不是一个多项式量级的数字，所以算法也不是多项式复杂度的
只要满足上述要求，都将其加入结果之中即可，代码如下:
code
class Solution {
void backtracking(vector<vector<int>> & res,vector<int> & temp,vector<int> & candidates,int remain,int start){
if(remain<0) return;
if(remain==0){
res.push_back(temp);
return;
}
for(int i=start;i<candidates.size();++i){
temp.push_back(candidates[i]);
backtracking(res,temp,candidates,remain-candidates[i],i);
temp.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int> & candidates, int target) {
vector<int> temp;
vector<vector<int>> res;
backtracking(res,temp,candidates,target,0);
return res;
}
};
此外，此题和卡特兰数有一些关系，即如果只是求解结果的组数，只需要将n带入卡特兰数公式即可。