p22

发表于 | 分类于 |

LeetCode 22 Generate Parentheses 题解

1.题目：

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:
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

题意：

输入一个数，给你这么多对括号，进行排列，要求所有的括号要配对。
输出所有的排列方式。

2.解题思路:

dp 设置一个count记录值得大小，’(‘为1,’)’为-1.
count不能小于0（即有一个右括号永远不能匹配到）
n=0,count=0,为合格的组。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 

public class Solution {
   public List<String> generateParenthesis(int n) {
		HashSet<String> hashSet=new HashSet<String>();
		List<String> ansList= new ArrayList<String>();
		dp(2*n,"",0,hashSet);
		for (String s:hashSet)
		{
			ansList.add(s);
			//System.out.println(s);
		}
		return ansList;
        
    }
	public void dp(int n,String str,int count,HashSet<String> hashSet) {
		
		//System.out.println(str);
		if (n==0)
		{
			if (count==0)
			{
				hashSet.add(str);
			}
			return;
		}
        if (count-1>=0)
        {
        	dp(n-1, str.concat(")"), count-1,hashSet);
        }
        dp(n-1, str.concat("("), count+1,hashSet);
    }
}

4.一些总结：