Parenthetical Possibilities

A string contains plain characters and parenthesised groups. Each group like (abc) means "choose exactly one of these characters here." Return all possible expansions, in the natural left-to-right, in-group order.

parentheticalPossibilities(s)

Groups never nest. A plain character is fixed.

Input format: the string. Output the expansions separated by ;.

Examples

"x(ab)"        // → "xa;xb"
"(ab)(cd)"     // → "ac;ad;bc;bd"
"abc"          // → "abc"

Walkthrough

Thinking it through

The string is a sequence of units read left to right: some fixed single characters, some groups offering several options. The output is every combination from picking one option per group, keeping fixed characters as-is, read in natural order.

Peeling off one unit at a time

The first unit — plain character or group — is independent of everything after it. Whatever you choose there, the rest still needs full expansion, producing its own list of suffixes. The answer is every combination of "a choice for the first unit" with "one expanded suffix."

If the string starts with (, the options are the characters inside, and the rest begins after the closing ). If it's a plain character, the only option is that character, and the rest begins at the next character.
Recursively expand everything after this unit.
For every option here, and every expansion of the remainder, glue the option onto the front — one final string per pair.

The base case

An empty string has exactly one expansion: the empty string. This lets the gluing work correctly all the way down — at the innermost level, prefixing the last unit's options onto the single empty-string expansion just yields the options themselves.

Why this produces exactly the right set, in the right order

Since every final string is built by one choice per unit, and the recursion visits units strictly left to right trying options in order, the nested "for each option, for each expansion of the rest" naturally produces expansions in the shown left-to-right order — the first group varies slowest (each choice starts a new block), later groups vary faster within each block.

Why not generate all combinations directly with nested loops

A fixed number of groups could use one nested loop per group — but the group count is only known at runtime and can vary. Recursion handles "however many groups happen to be here" without needing that count in advance: each call handles one unit and delegates the rest to itself.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.