Brace Expansion II: Recursive Set Operations

LeetCode 1096 asks you to take a brace expression like "{a,b}{c,{d,e}}" and generate every word it represents, sorted and without duplicates. Braces can nest arbitrarily deep, commas mean "union," and placing two groups side by side means "concatenation" (Cartesian product of two sets of strings). The output for that example is ["ac","ad","ae","bc","bd","be"].

This is LeetCode 1096: Brace Expansion II.

Why this problem matters

Brace Expansion II is a parsing problem disguised as a string problem. You need to handle nested grouping, two distinct operations (union and concatenation), and operator precedence, all without an explicit grammar specification. These are the same skills you use when building expression evaluators, template engines, or mini-compilers.

The problem also tests your ability to work with sets of strings as first-class values. Instead of computing a single number, every intermediate result is a set. Concatenation multiplies sets together (Cartesian product), and commas merge sets together (union). Thinking in terms of set algebra rather than individual strings is the conceptual shift that makes this problem click.

Finally, this is a hard-rated problem that becomes manageable once you recognize the pattern. The stack-based approach mirrors how you solve Basic Calculator or Decode String. If you already know those problems, Brace Expansion II is a natural extension into set-valued expressions.

The key insight

You can treat the brace expression like an arithmetic expression where:

• Concatenation plays the role of multiplication (Cartesian product of two string sets).
• Comma plays the role of addition (union of two string sets).
• Braces play the role of parentheses (grouping).

A stack lets you handle nesting. Each stack level holds two things: the current "product so far" (the set being built by concatenation) and a "pending union" accumulator (sets waiting to be merged when you hit a comma or closing brace).

When you encounter a letter, you concatenate it with the current set. When you see a comma, you dump the current set into the union accumulator and reset. When you see {, you push a new scope. When you see }, you finalize the union at this level, pop the stack, and concatenate the result with the level below.

The solution

class Solution:
    def braceExpansionII(self, expression: str) -> list[str]:
        stack = []
        current = {""}
        pending = set()

        for ch in expression:
            if ch == "{":
                stack.append((current, pending))
                current = {""}
                pending = set()
            elif ch == "}":
                pending |= current
                prev_current, prev_pending = stack.pop()
                current = {a + b for a in prev_current for b in pending}
                pending = prev_pending
            elif ch == ",":
                pending |= current
                current = {""}
            else:
                current = {s + ch for s in current}

        return sorted(pending | current)

The entire algorithm fits in about 15 lines. The stack stores tuples of (current_set, pending_union_set) for each nesting level. When you pop on a closing brace, you compute the Cartesian product between the level below and the resolved set at the current level. This naturally handles arbitrary nesting depth.

The current set tracks what you are actively building through concatenation. The pending set accumulates alternatives separated by commas. At the very end, you merge pending and current one final time and sort the result.

Visual walkthrough

The walkthrough above traces "{a,b}{c,{d,e}}" through the stack-based parser. Notice how each opening brace pushes a scope, each comma flushes the current set into the union accumulator, and each closing brace pops the scope and concatenates. The final result is sorted alphabetically.

Complexity analysis

The time complexity depends on the number of strings generated, which can be exponential in the worst case. Consider an expression like "{a,b}{c,d}{e,f}..." with n/4 groups of two alternatives each. That produces 2^(n/4) output strings, and each string has length proportional to n/4. The parsing itself is linear in the input length, but the set operations (concatenation and union) dominate because they produce and manipulate all output strings.

The space complexity is also O(2^(n/4)) because you need to store the full set of generated strings. In practice, duplicate elimination via sets helps when the expression produces many identical strings, but the worst-case bound remains exponential.

The building blocks

1. Stack-based expression parsing

The stack pattern for nested expressions appears across many LeetCode problems. The core idea: when you see an opening delimiter, push the current state and start fresh. When you see a closing delimiter, pop the saved state and combine it with what you just computed.

if ch == "{":
    stack.append((current, pending))
    current = {""}
    pending = set()
elif ch == "}":
    pending |= current
    prev_current, prev_pending = stack.pop()
    current = {a + b for a in prev_current for b in pending}
    pending = prev_pending

This is the same skeleton you use in Basic Calculator (push the running total and sign) or Decode String (push the running string and repeat count). The only difference is what "combine" means. Here it means Cartesian product of string sets.

2. Set union and Cartesian product

The two operations on string sets are the heart of this problem. Union is just set merge. Cartesian product concatenates every string in set A with every string in set B.

pending |= current

current = {a + b for a in prev_current for b in pending}

The set comprehension {a + b for a in A for b in B} is a clean Pythonic way to express Cartesian product with string concatenation. Using a set automatically handles deduplication, so you never need to worry about producing the same word twice.

Edge cases

• Single letter with no braces, like "a". The loop just concatenates "a" to {""} to get {"a"}. No stack operations needed.
• Nested braces with no commas, like "{{a}}". Each brace pair pushes and pops, but since there is no comma, pending stays empty and current passes through unchanged.
• Duplicates from different paths, like "{a,a}". The set automatically deduplicates, so the output is ["a"] rather than ["a","a"].
• Deep nesting, like "{a,{b,{c,{d}}}}". Each level pushes onto the stack. The stack depth equals the maximum nesting level, which is at most n/2.
• Adjacent groups without braces, like "ab". Each letter concatenates onto the current set: {""} -> {"a"} -> {"ab"}.

From understanding to recall

The trick to remembering this solution is understanding the analogy to arithmetic expressions. Concatenation is multiplication, comma is addition, and braces are parentheses. Once that mental model is solid, the stack-based approach writes itself because it is the same approach you use for any expression evaluator.

Practice by first implementing the solution for simple cases like "{a,b}c" and "a{b,c}" before tackling nested expressions. Build confidence that the push/pop logic handles one level of braces correctly, then nested cases follow naturally.

When you revisit this problem during spaced repetition, start by writing the four-branch skeleton (letter, comma, open brace, close brace) from memory. The set operations are the details that fill in each branch. If you can reconstruct the skeleton and remember that closing braces do a Cartesian product with the level below, you have the full solution.

Related posts

• Basic Calculator - The classic stack-based expression evaluator that uses the same push/pop pattern for nested parentheses
• Generate Parentheses - Recursive generation of all valid groupings, building intuition for brace nesting
• Decode String - Another stack-based string builder where brackets define nested scope and repetition

Every hard parsing problem on LeetCode boils down to the same stack pattern: push on open, pop on close, and define what "combine" means for your specific problem. CodeBricks helps you internalize that pattern so you can adapt it instantly to new variations.