leetcode/code/lc22.java at master · mJackie/leetcode · GitHub

History

67 lines (61 loc) · 2.06 KB

Raw

package code;

* 22. Generate Parentheses

* 题意：正确括号组合

* 难度：Medium

* 分类：String, Backtracking

* 思路：回溯法的典型题目，按选优条件向前搜索，达到目标后就退回一步或返回

* 注意：递归法别忘了两块的拼接，例如n=4时，可以由2，2拼起来作为答案

* lc32, lc22, lc301

import java.util.ArrayList;

import java.util.HashSet;

import java.util.List;

import java.util.Set;

public class lc22 {

public static void main(String[] args) {

System.out.println(generateParenthesis2(4));

}

public static List<String> generateParenthesis(int n) {

//递归法

Set<String> res = new HashSet<String>();

if(n==1) {

res.add("()");

return new ArrayList(res);

}

List<String> temp = generateParenthesis(n-1);

// 一个括号，和n-1个括号的组合

for (int i = 0; i < temp.size(); i++) {

res.add("("+temp.get(i)+")");

res.add("()"+temp.get(i));

res.add(temp.get(i)+"()");

}

//2块拼一起

for (int j = 2; j <=n/2 ; j++) {

List<String> temp1 = generateParenthesis(j);

List<String> temp2 = generateParenthesis(n-j);

for (int i = 0; i <temp1.size() ; i++) {

for (int k = 0; k < temp2.size(); k++) {

res.add(temp1.get(i)+temp2.get(k));

res.add(temp2.get(k)+temp1.get(i));

}

return new ArrayList(res);

}

public static List<String> generateParenthesis2(int n) {

//回溯法

ArrayList<String> res = new ArrayList<>();

backtracking(res,"", 0, 0, n);

return res;

}

public static void backtracking(List<String> list,String str,int left, int right, int max){

if(right==max){

list.add(str);

}

if(left<max)

backtracking(list,str+"(",left+1,right,max);

if(right<left)

backtracking(list,str+")",left,right+1,max);

}

leetcode/code/lc22.java at master · mJackie/leetcode · GitHub

Expand file tree

Breadcrumbs

lc22.java

Latest commit

History

Breadcrumbs

lc22.java

File metadata and controls