题目描述:
给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。 例如，给出n=3，解集为： “((()))”, “(()())”, “(())()”, “()(())”, “()()()”
解题思路： 对于回归问题，到现在也不太会使。看了其他同学的解答才明白一点，讲一下代码的思路吧。l和r分别代表字符串中剩余‘(’和‘)’的个数，当剩余左括号的个数大于右括号时，肯定不是合法的组合，直接返回；当剩余左括号的个数小于等于右括号的个数时，可以增加左括号，也可以增加右括号。
class Solution { public: /** * * @param n int整型 * @return string字符串vector */ vector<string> generateParenthesis(int n) { vector<string>ans; if(n==0){ return ans; } backPath(n,n,"",ans); return ans; } void backPath(int l, int r, string str, vector<string>& ans){ if(l>r||l<0||r<0) return; if(l==0&&r==0){ ans.push_back(str); return; } if(l<=r&&l!=0){ backPath(l-1, r,str+'(', ans); } if(l<r){ backPath(l,r-1,str+')', ans); } return; } };【既过不恋】
