欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法:回溯二 生成有效括号对Generate Parentheses

程序员文章站 2024-01-04 11:11:58
...

说明

地址: 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:

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

解法

解析:
生成有效括号,满足如下条件

  1. 左括号个数left要大于等于右括号数right, 也就是必须 right>left才能添加右括号。
  2. 左右括号剩余数要大于0.
  3. 回溯退出条件为if (left == 0 && right == 0)
package backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// https://leetcode.com/problems/generate-parentheses/
public class GenerateParentheses {

  public static void main(String[] args) {
    GenerateParentheses obj = new GenerateParentheses();
    List<String> result = obj.generateParenthesis(3);
    System.out.println("result > " + Arrays.toString(result.toArray()));
  }

  public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    if (n <= 0) {
      return result;
    }

    helper(result, "", n, n);

    return result;
  }

  public void helper(List<String> result, String combine, int left, int right) {
    //exit
    if (left == 0 && right == 0) {
      result.add(combine);
      return;
    }

    if (left > 0) {
      helper(result, combine + '(', left - 1, right);
    }
    if (right > left) {
      helper(result, combine + ')', left, right - 1);
    }
  }
}


代码下载

https://github.com/zgpeace/awesome-java-leetcode/blob/master/code/LeetCode/src/backtracking/GenerateParentheses.java

相关标签: 算法

上一篇:

下一篇: