def numTilePossibilities(self, tiles: str):
# Store the possible sequences in a set to ensure no duplicates
# Perform depth-first search
# current is an array of tiles chosen so far
# remaining is an array of remaining tiles
def find_possibilities(current, remaining):
# If current is non-empty, it is a valid sequence.
# Convert it to string and add to sequences.
sequences.add("".join(current))
# If there are no letters remaining, we have exhausted all possible
# sequences in this subtree and can return.
# For each letter in remaining, add it to current and find
# possibilities that start with letters in the new current.
for i in range(len(remaining)):
current.append(remaining[i])
find_possibilities(current, remaining[:i] + remaining[i+1:])
# After finding possibilities for new current, reset current
# by popping the last-added letter, before appending the next
# letter in remaining. This is the backtracking step.
# Kick off our search by providing an empty array for current and
# the original tiles string containing possible letters.
find_possibilities([], tiles)
# Return the number of unique sequences that we found from our search.