> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/backtracking/1087.-brace-expansion.md).

# 1087. Brace Expansion

A string `S` represents a list of words.

Each letter in the word has 1 or more options.  If there is one option, the letter is represented as is.  If there is more than one option, then curly braces delimit the options.  For example, `"{a,b,c}"` represents options `["a", "b", "c"]`.

For example, `"{a,b,c}d{e,f}"` represents the list `["ade", "adf", "bde", "bdf", "cde", "cdf"]`.

Return all words that can be formed in this manner, in lexicographical order.

**Example 1:**

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

**Example 2:**

```
Input: "abcd"
Output: ["abcd"]
```

**Note:**

1. `1 <= S.length <= 50`
2. There are no nested curly brackets.
3. All characters inside a pair of consecutive opening and ending curly brackets are different.

```cpp
// Recursive Backtracking
void helper(const string& s, int idx, string& cur, vector<string>& res) {
    if (idx == s.length()) {
        if (!cur.empty()) res.push_back(cur);
        return;
    }
    char c = s[idx];
    if (c == '{') {
        string chars; // potential character options
        int curIdx = idx + 1;
        while (curIdx < s.length() && s[curIdx] != '}') {
            if (s[curIdx] >= 'a' && s[curIdx] <= 'z') chars.push_back(s[curIdx]);
            ++curIdx;
        }
        // sorting for lexicographical order
        sort(chars.begin(), chars.end());
        // backtracking
        for (char ch : chars) {
            cur.push_back(ch);
            helper(s, curIdx + 1, cur, res);
            cur.pop_back();
        }
    } else if (c >= 'a' && c <= 'z') {
        cur.push_back(c);
        helper(s, idx + 1, cur, res);
        cur.pop_back();
    }
}
vector<string> expand(string S) { // time: O(2^n); space: O(n)
    string cur;
    vector<string> res;
    helper(S, 0, cur, res);
    return res;
}
```