07月16日, 2015 1,311 views次
链接:https://leetcode.com/problems/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:
"((()))", "(()())", "(())()", "()(())", "()()()"
题意:给定括号的对数,返回所有可以一一配对的括号字符串序列
分析:DFS搜索即可,设定'(‘为1,’)’为-1,则所有符合条件的序列最终结果为0。当DFS递归的时候,不可能得到值<0或者>n的情况,应当剪枝或回溯。
CPP代码:
class Solution { public: void DFS(string s, int cur, int n) { if(s.size() == 2 * n) { if(!cur) res.push_back(s); return; } if(cur > 0) DFS(s + ')', cur-1, n); if(cur < n) DFS(s + '(', cur+1, n); } vector<string> generateParenthesis(int n) { DFS("", 0, n); return res; } private: vector<string> res; };