22. Generate paranthesis

22_solution1_recursion.c

#include <stdlib.h>
#include <string.h>

typedef struct {
    char **items;
    int size;
} Result;

// each call gets its own copy of the prefix, like passing a string by value
static void build(int n, int opened, int closed, const char *cur, Result *res) {
    int len = opened + closed;
    if (closed == n) { // implies opened == n too
        res->items[res->size++] = strdup(cur);
        return;
    }

    char next[2 * n + 1];
    memcpy(next, cur, len);
    next[len + 1] = '\0';

    if (opened < n) {
        next[len] = '(';
        build(n, opened + 1, closed, next, res);
    }
    if (closed < opened) {
        next[len] = ')';
        build(n, opened, closed + 1, next, res);
    }
}

// Catalan(n) = C(2n, n) / (n + 1), computed iteratively
static long catalan(int n) {
    long c = 1;
    for (int i = 0; i < n; i++)
        c = c * 2 * (2 * i + 1) / (i + 2);
    return c;
}

char **generateParenthesis(int n, int *returnSize) {
    Result res = {malloc(catalan(n) * sizeof(char *)), 0};
    build(n, 0, 0, "", &res);
    *returnSize = res.size;
    return res.items;
}

22_solution2_backtracking.c

#include <stdlib.h>
#include <string.h>

typedef struct {
    char **items;
    int size;
} Result;

static void backtrack(int n, int opened, int closed, char *cur, Result *res) {
    int len = opened + closed;
    if (closed == n) { // implies opened == n too
        cur[len] = '\0';
        res->items[res->size++] = strdup(cur); // copies once, only for finished answers
        return;
    }

    if (opened < n) {
        cur[len] = '(';                          // choose
        backtrack(n, opened + 1, closed, cur, res); // explore
        // undo is implicit: len is derived from the counters, so the next
        // write simply overwrites this slot
    }

    if (closed < opened) {
        cur[len] = ')';
        backtrack(n, opened, closed + 1, cur, res);
    }
}

// Catalan(n) = C(2n, n) / (n + 1), computed iteratively
static long catalan(int n) {
    long c = 1;
    for (int i = 0; i < n; i++)
        c = c * 2 * (2 * i + 1) / (i + 2);
    return c;
}

char **generateParenthesis(int n, int *returnSize) {
    Result res = {malloc(catalan(n) * sizeof(char *)), 0};
    char *cur = malloc(2 * n + 1);
    backtrack(n, 0, 0, cur, &res);
    free(cur);
    *returnSize = res.size;
    return res.items;
}

22_solution1_recursion.cpp

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
  vector<string> generateParenthesis(int n) {
    vector<string> res;
    build(n, 0, 0, "", res);
    return res;
  }

private:
  void build(int n, int opened, int closed, string cur, vector<string> &res) {
    if (closed == n) { // implies opened == n too
      res.push_back(cur);
      return;
    }
    if (opened < n)
      build(n, opened + 1, closed, cur + '(', res);
    if (closed < opened)
      build(n, opened, closed + 1, cur + ')', res);
  }
};

22_solution2_backtracking.cpp

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
  vector<string> generateParenthesis(int n) {
    vector<string> res;
    string cur;
    cur.reserve(2 * n);
    backtrack(n, 0, 0, cur, res);
    return res;
  }

private:
  void backtrack(int n, int opened, int closed, string &cur,
                 vector<string> &res) {
    if (closed == n) {    // implies opened == n too
      res.push_back(cur); // copies once, only for finished answers
      return;
    }

    if (opened < n) {
      cur.push_back('(');                         // choose
      backtrack(n, opened + 1, closed, cur, res); // explore
      cur.pop_back();                             // undo
    }

    if (closed < opened) {
      cur.push_back(')');
      backtrack(n, opened, closed + 1, cur, res);
      cur.pop_back();
    }
  }
};

22_solution1_recursion.go

package main

func generateParenthesis(n int) []string {
    res := []string{}

    var build func(opened, closed int, cur string)
    build = func(opened, closed int, cur string) {
        if closed == n { // implies opened == n too
            res = append(res, cur)
            return
        }
        if opened < n {
            build(opened+1, closed, cur+"(")
        }
        if closed < opened {
            build(opened, closed+1, cur+")")
        }
    }

    build(0, 0, "")
    return res
}

22_solution2_backtracking.go

package main

func generateParenthesis(n int) []string {
    res := []string{}
    cur := make([]byte, 0, 2*n)

    var backtrack func(opened, closed int)
    backtrack = func(opened, closed int) {
        if closed == n { // implies opened == n too
            res = append(res, string(cur)) // copies once, only for finished answers
            return
        }

        if opened < n {
            cur = append(cur, '(')      // choose
            backtrack(opened+1, closed) // explore
            cur = cur[:len(cur)-1]      // undo
        }

        if closed < opened {
            cur = append(cur, ')')
            backtrack(opened, closed+1)
            cur = cur[:len(cur)-1]
        }
    }

    backtrack(0, 0)
    return res
}

22_solution1_recursion.java

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

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        build(n, 0, 0, "", res);
        return res;
    }

    private void build(int n, int opened, int closed, String cur, List<String> res) {
        if (closed == n) { // implies opened == n too
            res.add(cur);
            return;
        }
        if (opened < n)
            build(n, opened + 1, closed, cur + '(', res);
        if (closed < opened)
            build(n, opened, closed + 1, cur + ')', res);
    }
}

22_solution2_backtracking.java

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

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(n, 0, 0, new StringBuilder(2 * n), res);
        return res;
    }

    private void backtrack(int n, int opened, int closed, StringBuilder cur, List<String> res) {
        if (closed == n) { // implies opened == n too
            res.add(cur.toString()); // copies once, only for finished answers
            return;
        }

        if (opened < n) {
            cur.append('(');                            // choose
            backtrack(n, opened + 1, closed, cur, res); // explore
            cur.deleteCharAt(cur.length() - 1);         // undo
        }

        if (closed < opened) {
            cur.append(')');
            backtrack(n, opened, closed + 1, cur, res);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

22_solution1_recursion.js

class Solution {
  generateParenthesis(n) {
    const res = [];

    const build = (opened, closed, cur) => {
      if (closed === n) {
        // implies opened === n too
        res.push(cur);
        return;
      }
      if (opened < n) build(opened + 1, closed, cur + "(");
      if (closed < opened) build(opened, closed + 1, cur + ")");
    };

    build(0, 0, "");
    return res;
  }
}

22_solution2_backtracking.js

class Solution {
  generateParenthesis(n) {
    const res = [];
    const cur = [];

    const backtrack = (opened, closed) => {
      if (closed === n) {
        // implies opened === n too
        res.push(cur.join("")); // joins once, only for finished answers
        return;
      }

      if (opened < n) {
        cur.push("("); // choose
        backtrack(opened + 1, closed); // explore
        cur.pop(); // undo
      }

      if (closed < opened) {
        cur.push(")");
        backtrack(opened, closed + 1);
        cur.pop();
      }
    };

    backtrack(0, 0);
    return res;
  }
}

22_solution1_recursion.py

from typing import List


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []

        def build(opened: int, closed: int, cur: str) -> None:
            if closed == n:  # implies opened == n too
                res.append(cur)
                return
            if opened < n:
                build(opened + 1, closed, cur + "(")
            if closed < opened:
                build(opened, closed + 1, cur + ")")

        build(0, 0, "")
        return res

22_solution2_backtracking.py

from typing import List


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        cur = []

        def backtrack(opened: int, closed: int) -> None:
            if closed == n:  # implies opened == n too
                res.append("".join(cur))  # joins once, only for finished answers
                return

            if opened < n:
                cur.append("(")  # choose
                backtrack(opened + 1, closed)  # explore
                cur.pop()  # undo

            if closed < opened:
                cur.append(")")
                backtrack(opened, closed + 1)
                cur.pop()

        backtrack(0, 0)
        return res

22_solution1_recursion.rs

struct Solution;

impl Solution {
    fn generate_parenthesis(n: i32) -> Vec<String> {
        let mut res = Vec::new();
        Self::build(n, 0, 0, String::new(), &mut res);
        res
    }

    fn build(n: i32, opened: i32, closed: i32, cur: String, res: &mut Vec<String>) {
        if closed == n {
            // implies opened == n too
            res.push(cur);
            return;
        }
        if opened < n {
            Self::build(n, opened + 1, closed, format!("{cur}("), res);
        }
        if closed < opened {
            Self::build(n, opened, closed + 1, format!("{cur})"), res);
        }
    }
}

22_solution2_backtracking.rs

struct Solution;

impl Solution {
    fn generate_parenthesis(n: i32) -> Vec<String> {
        let mut res = Vec::new();
        let mut cur = String::with_capacity(2 * n as usize);
        Self::backtrack(n, 0, 0, &mut cur, &mut res);
        res
    }

    fn backtrack(n: i32, opened: i32, closed: i32, cur: &mut String, res: &mut Vec<String>) {
        if closed == n {
            // implies opened == n too
            res.push(cur.clone()); // copies once, only for finished answers
            return;
        }

        if opened < n {
            cur.push('('); // choose
            Self::backtrack(n, opened + 1, closed, cur, res); // explore
            cur.pop(); // undo
        }

        if closed < opened {
            cur.push(')');
            Self::backtrack(n, opened, closed + 1, cur, res);
            cur.pop();
        }
    }
}