1079: Letter-Tile-Possibilities
Medium

This week seems to be the week of the backtracking.

A simple recursion algorithm would suffice; just create an array of size 26 to hold the count of each letter of the alphabet, and iterate through all possibilities at each index.

Code:

class Solution {
public:
    int recursion(int index, int length, int *a) {
        if (index == length) return 0;
        int ans = 0;
        for (int i = 0; i < 26; ++i) {
            if (a[i] == 0) continue;
            --a[i];
            ++ans;
            ans += recursion(1, length, a);
            ++a[i];
        }
        return ans;
    }
    int numTilePossibilities(string tiles) {
        int a[26] = {0};
        for (char c : tiles) ++a[c-'A'];
        int ans = 0;
        for (int i = 0; i < 26; ++i) {
            if (a[i] == 0) continue;
            --a[i];
            ++ans;
            ans += recursion(1, tiles.size(), a);
            ++a[i];
        }
        return ans;
    }
};

Complexity:

Learnings:

Time Taken: