LeetCode22- Generate Parentheses

Dylan Liu

发布于 2019-07-01 11:58:20

2720

发布于 2019-07-01 11:58:20

文章被收录于专栏：dylanliudylanliu

Description

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:

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

Solution

package com.dylan.leetcode;

import java.util.LinkedList;
import java.util.List;

import org.junit.Test;

/**
 * Created by liufengquan on 2018/8/1.
 */
public class GenerateParentheses {
    List<String> strings = new LinkedList<>();
    public List<String> generateParenthesis(int n) {

        generate(new StringBuilder(), n, n);

        return strings;
    }

    private void generate(StringBuilder sb, int left, int right) {
        if (left == 0) {
            StringBuilder stringBuilder = new StringBuilder(sb);
            while (right > 0) {
                stringBuilder.append(")");
                right--;
            }
            strings.add(stringBuilder.toString());
            return;
        }
        if (right > left) {
            sb.append(")");
            generate(sb, left, right -1);
            sb.deleteCharAt(sb.length() - 1);
        }
        sb.append("(");
        generate(sb, left - 1, right);
        sb.deleteCharAt(sb.length() - 1);
    }

    @Test
    public void test() {
        List<String> list = generateParenthesis(3);
        printList(list);
    }

    private void printList(List<String> list) {
        for (String s : list) {
            System.out.println(s);
        }
        System.out.println();
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

combinations