leetcode 22. Generate Parentheses DFS深度优先遍历

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递归遍历即可实现，也可以使用栈实现，不说了，直接上代码：

import java.util.ArrayList; import java.util.List; /* * 递归遍历实现 * */ public class Solution { Character []record; List<String> resList=new ArrayList<String>(); public List<String> generateParenthesis(int n) { record=new Character[2*n]; getAll(0,n,n); return resList; } public void getAll(int k, int left, int right) { if(left==0 && right==0) { StringBuilder builder=new StringBuilder(); for(int i=0;i<record.length;i++) builder.append(record[i]); resList.add(builder.toString()); }else { if(left>0) { record[k]='('; getAll(k+1, left-1, right); } if(left<right) { record[k]=')'; getAll(k+1, left, right-1); } } } public static void main(String[] args) { Solution solution=new Solution(); System.out.println(solution.generateParenthesis(3)); } }

C++的做法如下，就是一个简单的DFS深度优先遍历。

代码如下：

#include <iostream> #include <vector> #include <string> using namespace std; class Solution { public: vector<string> res; vector<string> generateParenthesis(int n) { getByDFS(n, n,""); return res; } void getByDFS(int in, int out,string a) { if (in==0 && out==0) { string one = a; res.push_back(one); } else { if (in > 0) getByDFS(in - 1, out, a+"("); if(in < out) getByDFS(in , out-1, a + ")"); } } };