Hard · backtracking

Generate Parentheses

You already wrote one backtracker — All Permutations chose from n values and undid its choice. This one chooses between exactly two characters, but the counters that guard each branch (open < n, close < open) do the pruning a used[] array did before.

At a glanceRecurse over positions: place <code>'('</code> if <code>open &lt; n</code>, place <code>')'</code> if <code>close &lt; open</code>; at position 2n, print. Trying '(' first yields lexicographic order for free.

Problem

Input: One integer n (1 ≤ n ≤ 8).

Output: Every valid string of n pairs, one per line, in the order produced by trying '(' before ')' (lexicographic).

Samples:

InputOutput
2(())
()()
1()

For n = 3 there are 5 valid strings out of 2^6 = 64 raw combinations — the two counter rules throw away 59 of them without ever building them. That is pruning: rejecting a branch before walking it.

Your solution

main.cpp — your solution
Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Validity is two local rules

A prefix can grow into a valid string exactly when (1) it has used fewer than n opens, and (2) every ')' it contains is matched — which reduces to close < open at every step. Two integer counters carry both facts; no stack, no validation pass at the end. The rules check as you go, which is why the tree prunes itself.

Hint 2 — The base case prints the buffer

When pos == 2 * n the buffer is a complete string — and it is valid by construction, because the counters never allowed anything else. Print it with a newline and return. Notice there is no validation step anywhere: correctness came from the branching rules, not from a check.

Hint 3 — Order of the two attempts = output order

Inside the function, try '(' first and ')' second. Depth-first with that order visits the strings exactly in lexicographic order — the same free lunch as All Permutations. Swap the two branches and every line of your output reorders itself.

Solution (try it first!) 
#include <iostream>
using namespace std;

int n;
char buf[20];

void generate(int pos, int open, int close) {
    if (pos == 2 * n) {
        for (int i = 0; i < pos; i++) cout << buf[i];
        cout << endl;
        return;
    }
    if (open < n) {
        buf[pos] = '(';
        generate(pos + 1, open + 1, close);
    }
    if (close < open) {
        buf[pos] = ')';
        generate(pos + 1, open, close + 1);
    }
}

int main() {
    cin >> n;
    generate(0, 0, 0);
    return 0;
}

This is backtracking with pruning in its purest form: the search space is 2^(2n) raw, the counters cut it to the Catalan number — about 4^n / n^1.5 — without a single wasted branch. The family is growing: choices from a set in All Permutations, choices under constraints here. Next relatives: subsets with a sum condition, N-queens, sudoku.

Deep dive

Why this works

Two counters encode the whole validity predicate: fewer than n opens used, and never more closes than opens. Branching under those guards means every leaf of the search tree is valid by construction — no post-validation, and the tree is pruned before walking (2^(2n) raw strings collapse to the Catalan number).

The cost

O(Catalan(n) × n) time — about 4^n / n^1.5 strings, each printed in O(n) — and O(n) depth of recursion. n = 8 gives 1430 strings; the raw 2^(2n) = 65536 would be tried only if you validated at the end instead of pruning on the way.

Where it goes wrong

  • Loosening close < open to close < n prints invalid strings — the guard is the whole algorithm.
  • Forgetting to print at pos == 2n (or printing inside the branches) yields partial prefixes or duplicates.
  • Trying ')' first reorders the output; the judge compares sequences, so attempt order matters as much as validity.

Next step

Same skeleton, richer rules: choices from a set in All Permutations, choices under two counters here. The natural next branches: subsets with a sum target, N-queens.

Two things to remember

  • Pruning = rejecting a branch before walking it; two counters suffice here.
  • DFS attempt order defines output order — '(' before ')' gives lexicographic for free.
🐞 This version fails — open it and try

Checks close < n instead of close < open — invalid strings slip in

#include <iostream>
using namespace std;

int n;
char buf[20];

void generate(int pos, int open, int close) {
    if (pos == 2 * n) {
        for (int i = 0; i < pos; i++) cout << buf[i];
        cout << endl;
        return;
    }
    if (open < n) {
        buf[pos] = '(';
        generate(pos + 1, open + 1, close);
    }
    if (close < n) {   // bug: should be close < open
        buf[pos] = ')';
        generate(pos + 1, open, close + 1);
    }
}

int main() {
    cin >> n;
    generate(0, 0, 0);
    return 0;
}