Sandbox::https://github.com/prashanthigupta/leetcode-algorithms/blob/master/src/GenerateParentheses.java

Repository navigation

// https://leetcode.com/problems/generate-parentheses

// T: O(Catalan-number(n)) or O(4^n/sqrt(n))

// S: O(Catalan-number(n)) or O(4^n/sqrt(n))

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

public class GenerateParentheses {

private static final Map<Integer, List<String>> VALID_PARENTHESES = new HashMap<>();

static {

VALID_PARENTHESES.put(0, List.of(""));

VALID_PARENTHESES.put(1, List.of("()"));

for (int i = 2 ; i <= 8 ; i++) {

addValidParentheses(i);

}

private static void addValidParentheses(int i) {

final List<String> result = new ArrayList<>();

addValidParentheses(i, result);

VALID_PARENTHESES.put(i, result);

}

private static void addValidParentheses(int i, List<String> result) {

for (int k = 0 ; k < i ; k++) {

for (String s1 : VALID_PARENTHESES.get(i - k - 1)) {

for (String s2 : VALID_PARENTHESES.get(k)) {

result.add("(" + s1 + ")" + s2);

}

public List<String> generateParenthesis(int n) {

return VALID_PARENTHESES.get(n);

}