784. Letter Case Permutation

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Examples:
Input: S = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"
Output: ["3z4", "3Z4"]

Input: S = "12345"
Output: ["12345"]

Note:

• S will be a string with length between 1 and 12.

• S will consist only of letters or digits.

void helper(vector<string>& res, string cur, int pos) {
    if (pos == cur.length()) {
        res.push_back(cur);
        return;
    }
    if (cur[pos] >= '0' && cur[pos] <= '9') {
        helper(res, cur, pos + 1);
    } else {
        cur[pos] = tolower(cur[pos]);
        helper(res, cur, pos + 1);
        cur[pos] = toupper(cur[pos]);
        helper(res, cur, pos + 1);
    }
}
vector<string> letterCasePermutation(string S) { // time: O(2^n); space: O(2^n)
    vector<string> res;
    string cur = S;
    helper(res, cur, 0);
    return res;
}