Given a string s representing a list of words, where each letter can be replaced by a group of letters inside braces {a,b,c}, return all possible words in sorted order.

For example, "{a,b}c{d,e}f" means the first letter can be a or b, the second is c, the third can be d or e, and the fourth is f.

Examples

Example 1:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

Example 2:

Input: s = "abcd"
Output: ["abcd"]

Constraints

  • 1 <= s.length <= 50
  • s consists of {, }, ,, and lowercase English letters
  • s is guaranteed to be a valid brace expression

Thinking Process

Two-Phase Approach

Phase 1: Parse the string into a list of “groups.” Each group is either:

  • A single character (literal like c)
  • A sorted list of characters (options like {a,b})

Phase 2: Backtrack through the groups, picking one character from each, to generate all combinations.

Why Sort Each Group?

The problem requires the output in sorted order. If we sort each group’s options during parsing, then the DFS generates results in lexicographic order naturally – no post-sort needed.

Walk-through

s = "{a,b}c{d,e}f"

Parse → groups = [[a,b], [c], [d,e], [f]]

DFS tree:
  [a,b] → a → [c] → c → [d,e] → d → [f] → f → "acdf"
                                → e → [f] → f → "acef"
        → b → [c] → c → [d,e] → d → [f] → f → "bcdf"
                                → e → [f] → f → "bcef"

Output: ["acdf", "acef", "bcdf", "bcef"]
Backtracking tree start choose → explore → undo (prune)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Choose / explore / unchoose (this problem) O(2^n) O(n) Subsets, combinations
Constraint pruning Reduced search O(n) Early exit on invalid partial
Sort + skip duplicates O(2^n) O(n) Combination sum II style
Path recording O(n!) worst O(n) Permutations

Solution

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

Solution Explanation

Approach: Choose / explore / unchoose (this problem)

Key idea: ### Two-Phase Approach

How the code works: Phase 1: Parse the string into a list of “groups.” Each group is either:

  • A single character (literal like c)
  • A sorted list of characters (options like {a,b}) Phase 2: Backtrack through the groups, picking one character from each, to generate all combinations.

Walkthrough — input s = "{a,b}c{d,e}f", expected output ["acdf","acef","bcdf","bcef"]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Common Mistakes

  • Forgetting to skip commas during parsing (adding , as a character option)
  • Not sorting groups, then needing to sort the entire output (O(k^m · m log(k^m)) instead of O(k^m · m))
  • Off-by-one: not incrementing i past the closing }

Key Takeaways

  • “Generate all combinations from groups of choices” = backtracking over groups
  • Parsing into an intermediate representation (groups) cleanly separates concerns from the combinatorial generation
  • Sorting inputs early often eliminates the need to sort outputs

References

Template Reference