CodingGyan

Generate Balanced Parentheses

medium Recursion and Backtracking

Problem

Read n. Print all different strings of n pairs of parentheses that are balanced, one per line, in dictionary order where ( comes before ).

Constraints

  • 1 <= n <= 8

Examples

Input

2

Output

(())
()()

Solutions

Best approachTime O(Catalan(n) * n)Space O(n)

Instead of making all 2^(2n) strings and checking them, we only add a character when the string can still become valid. This is backtracking: grow the answer, and stop a branch as soon as it cannot work. The number of results is the Catalan number.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process a number.
 * Input   : One integer n.
 * Output  : All balanced strings.
 * Approach: Backtracking.
 * Time    : O(Catalan(n) * n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: Build the string step by step. open = how many ( we used. close = how many ) we used.
        static void build(String current, int open, int close, int pairs, java.util.List<String> result) {
            // Step 2: Base case. The string has 2 * pairs characters: save it.
            if (current.length() == 2 * pairs) {
                result.add(current);
                return;
            }

            // Step 3: We may add ( while we have not used all pairs. We try ( first, so the output is in dictionary order.
            if (open < pairs) {
                build(current + "(", open + 1, close, pairs, result);
            }

            // Step 4: We may add ) only if there is an open ( that is not closed yet.
            if (close < open) {
                build(current + ")", open, close + 1, pairs, result);
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(long n) {
        java.util.List<String> result = new java.util.ArrayList<>();
        build("", 0, 0, (int) n, result);
        return result.toArray(new String[0]);
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(String.join("\n", solve(n)));
    }
}
Hints (1)
  1. When may we add a closing parenthesis?

Try these next