LeetCode 22. Generate Parentheses Elixir solution

LeetCode problem link: 22. Generate Parentheses

You can find the problem description, deep-dive explanation, and solutions in C++, Java, JS, TS and Python programming languages supported by LeetCode here

LeetCode 22. Generate Parentheses: short description of the solution

The Elixir solution uses the Backtracking technique to build valid parentheses combinations recursively. It adds ( while open < n and adds ) only when close < open, preventing invalid combinations from being generated. When open == n and close == n, the completed combination is added to the result. The number of valid combinations follows the Catalan number Cn. The time complexity is O(n * C_n), with O(n) auxiliary space for recursion.

Patterns | Techniques | Data Structures

Backtracking technique
Recursion

Complexity

Time complexity: O(n * Cn)
Space complexity: O(n)

! See the detailed complexity analysis here

LeetCode 22. Generate Parentheses: Elixir solution

defmodule Solution do
  @spec generate_parenthesis(n :: integer) :: [String.t()]
  def generate_parenthesis(n) do
    backtrack(n, 0, 0, "", [])
  end

  # All n pairs have been used
  defp backtrack(n, n, n, current, result) do
    [current | result]
  end

  defp backtrack(n, open, close, current, result) do
    # Add '(' if we still have opening parentheses available
    result =
      if open < n do
        backtrack(n, open + 1, close, current <> "(", result)
      else
        result
      end

    # Add ')' only if it does not make the combination invalid
    if close < open do
      backtrack(n, open, close + 1, current <> ")", result)
    else
      result
    end
  end
end