Solution for Leetcode problem 1079: Letter Tile Possibilities

In this problem, we are asked to count all the combinations of words we can make out of letters “tiles”. This is equivalent to all the combinations that you can make in scrabbles. In particular, the maximum number of tiles you have is 7, just like scrabbles from what I remember.

Usually we should not generate all solutions in counting problems, because the number of combination can be exponential (or worse), and then we will run out of time. But, because the number of letters is so small, we are able to do this for this particular problem. There is probably a formula to find this number, and it would be faster, but I don’t know what the formula is, and therefore the computer will do the counting for me this time.

The solution is essentially a DFS, where each step is the equivalent of pulling one of the tile from the set of tiles we have. I don’t keep track of the current word since we are only asked about the number of different combinations. Since the tiles with the same letter on them are equivalent, and I don’t want to count a combination twice, I created a counting map at the start keyed on the unique characters and mapping to the count for each of them.

func numTilePossibilities(tiles string) int {
    myMap := make(map[rune]int)
    for _, c := range tiles {
        if _, ok := myMap[c]; ok {
            myMap[c] = myMap[c] + 1
        } else {
            myMap[c] = 1
        }
    }
    
    // discard empty string in the end
    return recPossibilities(myMap) - 1
}
func recPossibilities(myMap map[rune]int) int {
    res := 1
    for key, val := range myMap {
        if val > 0 {
            myMap[key] = val - 1
            res += recPossibilities(myMap)
            myMap[key] = val
        }
    }
    return res
}