Generate Div Tags

Tags

Generate Div Tags

Category

Recursion

Difficulty

Hard

Problem Statement

Given a positive integer n, generate all valid (properly nested and ordered) combinations of n pairs of <div> opening and </div> closing tags. Each combination must be a string where every opening tag has a corresponding closing tag, and tags are properly nested. Return all such combinations.

Intuition

This problem is structurally identical to generating all valid combinations of n pairs of parentheses. At any point during construction, we can place an opening <div> tag as long as we have not used all n opening tags, and we can place a closing </div> tag as long as the number of closing tags used so far is less than the number of opening tags used. This ensures every generated combination is valid. The total number of valid combinations is the nth Catalan number.

Approach

  1. Use a recursive function that tracks the number of opening tags placed and the number of closing tags placed.
  2. Base case: if both counts equal n, a complete valid combination has been formed — add it to the result list.
  3. Recursive case 1: if the number of opening tags placed is less than n, place an opening <div> tag and recurse.
  4. Recursive case 2: if the number of closing tags placed is less than the number of opening tags placed, place a closing </div> tag and recurse.
  5. Build the string incrementally (or use a list for efficiency) and return all valid combinations.

Pseudocode

function generateDivTags(numberOfTags):
    result = []
    generate(0, 0, numberOfTags, "", result)
    return result

function generate(openCount, closeCount, n, current, result):
    if closeCount == n:
        result.append(current)
        return

    if openCount < n:
        generate(openCount + 1, closeCount, n, current + "<div>", result)

    if closeCount < openCount:
        generate(openCount, closeCount + 1, n, current + "</div>", result)

Time & Space Complexity

  • Time: O(C(n) * 2n * tagLength) where C(n) is the nth Catalan number, approximately 4^n / (n^(3/2) * sqrt(pi)). There are C(n) valid combinations, each of length 2n tags. Building each string takes O(n) time with tag length overhead.
  • Space: O(C(n) * n) for storing all results. The recursion stack uses O(n) additional space.

Key Insights

  • This is the parentheses generation problem in disguise, with <div> replacing ( and </div> replacing ).
  • The constraint closeCount < openCount is what guarantees proper nesting — you can never close more tags than you have opened.
  • The number of valid combinations follows the Catalan number sequence: 1, 2, 5, 14, 42, 132, ... for n = 1, 2, 3, 4, 5, 6, ...
  • Using a list/array to build the string and joining at the end is more efficient than string concatenation in many languages.
  • The recursion tree naturally avoids invalid combinations, so no post-hoc validation is needed.

Edge Cases

  • n = 1 — only one combination: <div></div>.
  • n = 0 — should return an empty list or a list with an empty string, depending on the problem specification.
  • Large n — the number of results grows exponentially (Catalan numbers), so memory may become a concern for large inputs.
  • The distinction between this and parentheses is purely cosmetic; the combinatorial structure is identical.

Linked mentions