【Leetcode】22. Generate Parentheses总结

无情阅读：445 2022-03-12 16:24:44 评论：0

本文章主要介绍了【Leetcode】22. 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:

[ 
  "((()))", 
  "(()())", 
  "(())()", 
  "()(())", 
  "()()()" 
]

题意是求n组括号的组合方式，要求能够组成合理的左右括号。

分析：

所谓合理的组合方式，应该是左右括号数量相等，在初始情况下应该先添加左括号，在递归过程中左括号数量大于等于右括号的数量，我们记录左右括号的数量和当前字符串，如果左括号数量小于n，则字符串可以添加一个左括号，左括号数量增加一，进入下一轮递归；如果右括号数量小于左括号数量，则字符串添加一个右括号，右括号数量加一后进入下一轮递归。

函数原型：

dfs(String currentString, int leftCount, int rightCount, int n);

迭代的过程如下图所示：

代码：

import java.util.ArrayList; 
import java.util.List; 
 
/** 
 * Author: puyangsky 
 * Date: 17/4/27 
 * 方法：递归、回溯 
 */ 
public class L22GenerateParentheses { 
 
    private static List<String> list = new ArrayList<>(); 
 
    public static void dfs(List<String> list, String parenthesis, int left, int right, int count) { 
        if (parenthesis.length() == count * 2) {//达到最大长度，添加到结果中 
            list.add(parenthesis); 
            return; 
        } 
        //左括号仍然可以添加的情况 
        if (left < count) 
            dfs(list, parenthesis + "(", left + 1, right, count); 
 
		//右括号可以添加的情况 
        if (right < left) 
            dfs(list, parenthesis + ")", left, right + 1, count); 
    } 
 
    public static List<String> generateParenthesis(int n) { 
        dfs(list, "", 0, 0, n); 
        return list; 
    } 
 
 
    public static void main(String[] args) { 
        generateParenthesis(3); 
        for (String l : list) { 
            System.out.println(l); 
        } 
    } 
}