Algorithm (Recursive Descent)

1. The BNF grammar for this problem could be written as $$\begin{aligned} \texttt{Expr} & :=\texttt{End|Item|Item Expr}\\\\ \texttt{Item} & :=\texttt{Word|\{Expr(,…,Expr)\}}\end{aligned}$$
2. So it suffices to implement a recursive descent parser according to the BNF grammar.

Code

using int64 = long long;

class tokenizer {
 public:
  static constexpr char eof = '\n';
  int pos;
  int n;
  string str;

  tokenizer(const string & s) :  str(s.begin(), s.end()), pos(0), n(s.size()) {}

  bool has_next() {
    return !(peek() == eof);
  }

  char peek() {
    for (int i = pos; i < n; i++) {
      if (str[i] != ' ')
        return str[i];
    }
    return eof;
  }

  void consume() {
    pos++;
  };

  void trim_whitespace() {
    while (str[pos] == ' ') pos++;
  }

  char next_char() {
    trim_whitespace();
    return pos < n ? str[pos++] : eof;
  }

  string next_string() {
    string acc = "";
    trim_whitespace();
    while (isalpha(str[pos]) and pos < n)
      acc += str[pos++];
    return acc;
  };

  int64 next_number() {
    int sign = peek() == '-' ? -1 : 1;
    int64 acc = 0;
    while (peek() >= '0' and peek() <= '9') {
      acc = 10.0 * acc + (next_char() - '0');
    }
    return acc * sign;
  }
};


class Solution {
 public:
  vector<string> braceExpansionII(string expression) {
    /*
      Expr := End | Item | Item Expr
      Item := Word | {Expr} | {Expr,...,Expr}
     */
    tokenizer in(expression);

    auto Expr = std::function<unordered_set<string>(void)>{};
    auto Item = std::function<unordered_set<string>(void)>{};

    auto combine = [](unordered_set<string> a, unordered_set<string> b) {
      unordered_set<string> acc;
      for (const auto x : a)
        for (const auto y : b)
          acc.insert(x + y);
      return acc;
    };

    auto merge = [](unordered_set<string>* a, const unordered_set<string>& b) {
      std::copy(begin(b), end(b), std::inserter(*a, begin(*a)));
    };

    Expr = [&]() -> unordered_set<string> {
      if (in.peek() == tokenizer::eof)
        return {std::string{}};
      else {
        auto acc = combine(unordered_set<string>{std::string{}}, Item());
        if (in.peek() == '{' or isalpha(in.peek()))
          acc = combine(acc, Expr());
        return acc;
      }
    };

    Item = [&]() -> unordered_set<string> {
      if (isalpha(in.peek())) 
        return {in.next_string()};
      else if (in.peek() == '{') {
        auto acc = (in.next_char(), Expr());
        while (in.peek() == ',') 
          merge(&acc, (in.next_char(), Expr()));
        return (in.next_char(), acc);
      }
      else 
        throw std::domain_error("unmatched case");
    };

    const auto solution = [&](vector<string> self = {}) {
      const auto parsed = Expr();
      return (std::copy(begin(parsed), end(parsed), std::back_inserter(self)), 
              std::sort(begin(self), end(self)),
              self);
    }();

    return solution;

  }
};