Letter Tile Possibilities solution and explanation

def numTilePossibilities(tiles):
    from itertools import permutations
    tile_set = set()

    def backtrack(path, used):
        if path:
            tile_set.add(path)
        for i in range(len(tiles)):
            if used[i]:
                continue

            if i > 0 and tiles[i] == tiles[i-1] and not used[i-1]:
                continue

            used[i] = True
            backtrack(path + tiles[i], used)
            used[i] = False

    tiles = ''.join(sorted(tiles))
    backtrack('', [False]*len(tiles))

    return len(tile_set)

import java.util.*;

public class TilePossibilities {
    public int numTilePossibilities(String tiles) {
        Set<String> uniqueSequences = new HashSet<>();
        boolean[] used = new boolean[tiles.length()];
        char[] tileArr = tiles.toCharArray();
        Arrays.sort(tileArr);
        backtrack("", tileArr, uniqueSequences, used);
        return uniqueSequences.size();
    }

    private void backtrack(String path, char[] tiles, Set<String> results, boolean[] used) {
        if (!path.isEmpty()) {
            results.add(path);
        }
        for (int i = 0; i < tiles.length; ++i) {
            if (used[i] || (i > 0 && tiles[i] == tiles[i-1] && !used[i-1])) {
                continue;
            }
            used[i] = true;
            backtrack(path + tiles[i], tiles, results, used);
            used[i] = false;
        }
    }
}

#include <iostream>
#include <unordered_set>
#include <algorithm>

using namespace std;

void backtrack(string path, string& tiles, unordered_set<string>& results, vector<bool>& used){
    if (!path.empty()) {
        results.insert(path);
    }
    for (int i = 0; i < tiles.size(); ++i) {
        if (used[i] || (i > 0 && tiles[i] == tiles[i-1] && !used[i-1])) {
            continue;
        }
        used[i] = true;
        backtrack(path + tiles[i], tiles, results, used);
        used[i] = false;
    }
}

int numTilePossibilities(string tiles) {
    unordered_set<string> results;
    vector<bool> used(tiles.size(), false);
    sort(tiles.begin(), tiles.end());
    backtrack("", tiles, results, used);
    return results.size();
}

def numTilePossibilities(tiles):
    from collections import Counter

    def dfs(counter):
        count = 0
        for char in counter:
            if counter[char] > 0:
                counter[char] -= 1
                count += 1 + dfs(counter)
                counter[char] += 1
        return count

    tile_count = Counter(tiles)
    return dfs(tile_count)

import java.util.HashMap;
import java.util.Map;

public class TilePossibilities {
    public int numTilePossibilities(String tiles) {
        Map<Character, Integer> counter = new HashMap<>();
        for (char tile : tiles.toCharArray()) {
            counter.put(tile, counter.getOrDefault(tile, 0) + 1);
        }
        return dfs(counter);
    }

    private int dfs(Map<Character, Integer> counter) {
        int sum = 0;
        for (char c : counter.keySet()) {
            if (counter.get(c) > 0) {
                counter.put(c, counter.get(c) - 1);
                sum += 1 + dfs(counter);
                counter.put(c, counter.get(c) + 1);
            }
        }
        return sum;
    }
}

#include <iostream>
#include <unordered_map>
#include <algorithm>

using namespace std;

int dfs(unordered_map<char, int>& counter) {
    int sum = 0;
    for (auto& [key, value] : counter) {
        if (value > 0) {
            counter[key]--;
            sum += 1 + dfs(counter);
            counter[key]++;
        }
    }
    return sum;
}

int numTilePossibilities(string tiles) {
    unordered_map<char, int> counter;
    for (char tile : tiles) {
        counter[tile]++;
    }
    return dfs(counter);
}

function numTilePossibilities(tiles: string): number {
    const cnt: number[] = new Array(26).fill(0);
    for (const c of tiles) {
        ++cnt[c.charCodeAt(0) - 'A'.charCodeAt(0)];
    }
    const dfs = (cnt: number[]): number => {
        let res = 0;
        for (let i = 0; i < 26; ++i) {
            if (cnt[i] > 0) {
                ++res;
                --cnt[i];
                res += dfs(cnt);
                ++cnt[i];
            }
        }
        return res;
    };
    return dfs(cnt);
}

func numTilePossibilities(tiles string) int {
	cnt := [26]int{}
	for _, c := range tiles {
		cnt[c-'A']++
	}
	var dfs func(cnt [26]int) int
	dfs = func(cnt [26]int) (res int) {
		for i, x := range cnt {
			if x > 0 {
				res++
				cnt[i]--
				res += dfs(cnt)
				cnt[i]++
			}
		}
		return
	}
	return dfs(cnt)
}