1079. Letter Tile Possibilities

Reformulated question¶

Given a string of tile letters, count how many distinct non-empty sequences can be formed by using each tile at most once.

• Example: tiles="AAB" -> 8
  • Distinct sequences: A, B, AA, AB, BA, AAB, ABA, BAA

Key trick¶

Use backtracking on letter counts, not on tile indices.

• At each step:
  • pick any letter whose remaining count is positive
  • count that new sequence
  • recurse
  • restore the count
• This avoids generating duplicate permutations from repeated letters.

Trap¶

Common mistakes:

• Generating all permutations of positions and deduplicating with a set.
  • Works, but is wasteful.
• Forgetting that sequences can have any length from 1 to n.
• Double counting duplicates like the two A tiles in "AAB".

Why this question is interesting¶

It looks like permutations, but the real idea is DFS over a multiset.

• Good test of:
  • backtracking
  • duplicate handling
  • modeling with counts instead of raw arrays

Solve the problem with idiomatic python¶

from collections import Counter

def num_tile_possibilities(tiles: str) -> int:
    counts = Counter(tiles)

    def dfs() -> int:
        total = 0

        # Try placing each available letter next.
        for ch in counts:
            if counts[ch] == 0:
                continue

            # Using this letter creates one new non-empty sequence.
            total += 1

            counts[ch] -= 1
            total += dfs()
            counts[ch] += 1

        return total

    return dfs()

Library alternative:

• No standard-library function solves this exact counting problem directly with the same efficiency.

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("tiles", "expected"),
    [
        ("A", 1),
        ("AB", 4),
        ("AA", 2),
        ("AAB", 8),
        ("ABC", 15),
        ("AAABBC", 188),
        ("V", 1),
        ("AAAAAAA", 7),
    ],
)
def test_num_tile_possibilities(tiles, expected):
    assert num_tile_possibilities(tiles) == expected

Extra¶

First time I saw a recursion call inside a loop. I wasn't able to wrap my head arround this (while the code being small and simple). I ask AI for help telling I was missing something. Here's part of the responses.

You are not missing something small.

You are missing the model of what the program is doing.

Once that model is clear, recursion, DFS, and backtracking all become much less mysterious.

First: what is the program really exploring?¶

It is exploring all possible sequences you can build, one letter at a time.

For "AAB":

• Start with empty sequence: ""
• From there, you may add:
  • A
  • B

If you picked A, your sequence is now:

• "A"

From "A", you may still add:

• A again, making "AA"
• B, making "AB"

From "AA", you may still add:

• B, making "AAB"

From "AB", you may still add:

• A, making "ABA"

If you picked B first, your sequence is:

• "B"

From "B", you may still add:

• A, making "BA"

From "BA", you may still add:

• A, making "BAA"

So the whole exploration is:

""
├── "A"
│   ├── "AA"
│   │   └── "AAB"
│   └── "AB"
│       └── "ABA"
└── "B"
    └── "BA"
        └── "BAA"

Those are exactly the 8 sequences:

• A
• AA
• AAB
• AB
• ABA
• B
• BA
• BAA

Why this is called DFS¶

DFS means Depth-First Search.

It is not only for trees given in input.

It means:

• you have some state
• from that state, you can go to next states
• you explore one path as deep as possible before coming back

That is exactly what happens here.

The state is:

• what letters are still available

Or, if you prefer:

• the current built sequence
• plus the remaining counts

For "AAB":

• state 1: current "", remaining A:2, B:1
• state 2: current "A", remaining A:1, B:1
• state 3: current "AA", remaining A:0, B:1
• state 4: current "AAB", remaining A:0, B:0

That is one path.

DFS goes down that path fully before trying another one.

So the order is like:

• go to "A"
• then "AA"
• then "AAB"
• no more move possible
• go back
• try "AB"
• then "ABA"
• go back
• go back
• try "B"
• then "BA"
• then "BAA"

That is depth-first.

Why recursion inside a loop is normal here¶

The loop means:

• from the current state, try every possible next move

The recursive call means:

• after choosing one move, continue solving the smaller subproblem

That pattern is extremely common.

General shape:

for each possible choice:
    make that choice
    solve the rest recursively
    undo that choice

That is almost the definition of backtracking.

So recursion inside a loop is not weird here.

It is the natural way to say:

• "try each next option"
• "and from each option, keep exploring"

What backtracking means here¶

Backtracking means:

• choose something
• go deeper with that choice
• then undo the choice
• then try another choice

In your code:

counts[ch] -= 1
total += dfs()
counts[ch] += 1

This is the backtracking part.

Read it as:

• use one ch
• explore everything possible after using it
• put it back so other branches can use it

Example with "AAB".

Suppose current counts are:

A:2, B:1

You choose A:

A:1, B:1

Now you recursively explore all sequences starting with that A.

When done, you restore:

A:2, B:1

Now the program can try starting with B.

Without restoring, the next branch would be wrong.

So backtracking = "do, recurse, undo".

What exactly is being counted¶

This line:

total += 1

means:

• "the moment I choose one letter, I have formed one new non-empty sequence"

That is the most important line to understand.

Suppose current built sequence is:

• ""

If I choose A, I have formed:

• "A"

That is one valid sequence, so count +1.

Then I recurse to see if "A" can be extended to longer sequences:

• "AA"
• "AB"
• "AAB"
• "ABA"

Same idea if current sequence is "A".

If I choose B, I form:

• "AB"

That is one more valid sequence, so count +1.

Then recurse to extend "AB" into "ABA".

So the algorithm counts:

• all length-1 sequences
• all length-2 sequences
• all length-3 sequences
• ...
• up to length n

It does that naturally because every time you append one letter, you count the newly formed sequence.

Why duplicates are not counted¶

This is the other big idea.

You do not think of the tiles as separate objects like:

• first A
• second A
• B

Instead you think only in terms of counts:

• A:2
• B:1

So from the empty sequence, the possible next letters are only:

• A
• B

Not:

• first A
• second A
• B

That is why "A" is counted once, not twice.

If you were choosing tile positions, you might do:

• choose A at index 0 -> "A"
• choose A at index 1 -> "A"

That would duplicate the same sequence.

But with counts, there is only one branch called "choose A".

That is the whole trick.

Compare with the wrong mental model¶

Bad model:

• "I have 3 tiles: A1, A2, B"

Then from the start you might branch into:

• choose A1
• choose A2
• choose B

But choose A1 and choose A2 both produce the same visible sequence:

• "A"

So you would need a set or duplicate skipping.

Good model:

• "I have counts: A appears 2 times, B appears 1 time"

Then from the start the branches are only:

• choose A
• choose B

Now duplicates never appear.

Let us add the missing state: the current sequence¶

Your print only shows counts, but not the sequence being built.

That makes it much harder to follow.

The recursion becomes much clearer if you print the path.

Here is a version made for understanding:

from collections import Counter

def num_tile_possibilities(tiles: str) -> int:
    counts = Counter(tiles)

    def dfs(path: str) -> int:
        print(f"ENTER path={path!r}, counts={dict(counts)}")
        total = 0

        for ch in counts:
            if counts[ch] == 0:
                continue

            print(f"  choose {ch!r} from path={path!r}")

            counts[ch] -= 1
            new_path = path + ch

            print(f"  formed {new_path!r} -> +1")
            total += 1

            total += dfs(new_path)

            counts[ch] += 1
            print(f"  undo {ch!r}, back to path={path!r}, counts={dict(counts)}")

        print(f"RETURN path={path!r}, total={total}")
        return total

    return dfs("")

For "AAB", this matches the tree:

""
├── "A"
│   ├── "AA"
│   │   └── "AAB"
│   └── "AB"
│       └── "ABA"
└── "B"
    └── "BA"
        └── "BAA"

That tree is the recursion.

Now let us connect that to the total values in code¶

Here is the key:

total += 1
total += dfs()

Meaning:

• +1 for the sequence formed right now
• +dfs() for all longer sequences extending it

Example at root with A:

• choosing A creates "A" -> +1
• recursive call counts all extensions of "A":
  • "AA"
  • "AAB"
  • "AB"
  • "ABA"
• so the whole A branch contributes 5

That is why total is not just counting leaves.

It is counting every non-empty node in the tree.

Why the empty string is not counted¶

We start with an empty path "", but we do not count it.

We only count when we choose a letter:

total += 1

So:

• empty sequence "" is not counted
• every time we append one letter, we create one non-empty sequence and count it

That is exactly what the problem asks.

Why there is no explicit base case¶

You may expect something like:

if ...:
    return ...

But here the base case is implicit.

If no letter has positive count, then the loop does nothing:

for ch in counts:
    if counts[ch] == 0:
        continue

So total stays 0, and the function returns 0.

That means:

• "from this state, there are no more longer sequences to build"

For example at "AAB":

• counts are A:0, B:0
• no choice possible
• return 0

That is the stopping point.

Your trace is hard to read because one crucial thing is missing¶

Your trace prints:

• counts
• ch
• total

But not:

• the current sequence being built
• the recursion depth

Without those, many different calls look almost the same.

A much better debug version is this:

from collections import Counter

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        counts = Counter(tiles)

        def dfs(path: str, depth: int) -> int:
            indent = "  " * depth
            print(f"{indent}ENTER path={path!r}, counts={dict(counts)}")

            total = 0

            for ch in counts:
                if counts[ch] == 0:
                    continue

                print(f"{indent}choose {ch!r}")
                counts[ch] -= 1

                new_path = path + ch
                print(f"{indent}formed {new_path!r} -> +1")
                total += 1

                total += dfs(new_path, depth + 1)

                counts[ch] += 1
                print(f"{indent}undo {ch!r}, back to path={path!r}")

            print(f"{indent}RETURN path={path!r}, total={total}")
            return total

        return dfs("", 0)

This will show you:

• where you are in the tree
• what sequence has been built
• when you go deeper
• when you come back up

That is the easiest way to see DFS and backtracking.

The shortest correct intuition¶

If you want one compact mental model, use this:

• dfs(path) means:
  • "count all sequences that can be formed by extending path"

Inside it:

• try every possible next letter
• each next letter creates one new sequence immediately
• then recursively count longer sequences from there
• undo the choice to try the next letter

So the skeleton is:

for each next possible letter:
    use it
    count the new sequence
    count everything longer starting from it
    undo it

Tiny concrete example with "AA"¶

This one is even simpler.

Possible distinct sequences:

• A
• AA

Count = 2.

How the algorithm sees it:

Start:

• counts = A:2

Choose A:

• formed "A" -> +1

Recurse with counts A:1.

Choose A:

• formed "AA" -> +1

Recurse with counts A:0.

No more choices -> return 0.

So total:

• 1 + 1 = 2

Why not duplicate "A"?

• because there is only one branch "choose A"
• not two branches "choose first A" and "choose second A"

Tiny concrete example with "AB"¶

Possible sequences:

• A
• B
• AB
• BA

Count = 4.

Tree:

""
├── "A"
│   └── "AB"
└── "B"
    └── "BA"

Count all non-empty nodes:

• A
• AB
• B
• BA

So 4.

If you want, forget DFS and think "decision tree"¶

Sometimes "DFS" sounds too abstract.

You can think of it as a decision tree:

• every node = current sequence
• every edge = choose one next letter
• recursion = walking that tree
• depth-first = follow one branch fully before moving to the next
• backtracking = walk back up after finishing a branch

This problem becomes much easier if you picture that tree.

The code again, but annotated only with the meaning¶

from collections import Counter

def num_tile_possibilities(tiles: str) -> int:
    counts = Counter(tiles)

    def dfs() -> int:
        total = 0

        # Try each distinct letter that is still available.
        for ch in counts:
            if counts[ch] == 0:
                continue

            # Use one copy of ch.
            counts[ch] -= 1

            # We just formed one new non-empty sequence.
            total += 1

            # Count all longer sequences starting from this one.
            total += dfs()

            # Undo the choice so other branches start from the old state.
            counts[ch] += 1

        return total

    return dfs()

A hidden detail is:

• the current sequence is not stored explicitly
• but it is implicit in the decremented counts along the recursion path

For learning, it is often better to store it explicitly as path.

Best learning version¶

I recommend this version for understanding:

from collections import Counter

def num_tile_possibilities(tiles: str) -> int:
    counts = Counter(tiles)

    def dfs(path: str) -> int:
        total = 0

        for ch in counts:
            if counts[ch] == 0:
                continue

            counts[ch] -= 1
            new_path = path + ch

            print("formed:", new_path, "remaining:", dict(counts))

            total += 1
            total += dfs(new_path)

            counts[ch] += 1

        return total

    return dfs("")

For "AAB" it will print the actual sequences as they are formed:

• A
• AA
• AAB
• AB
• ABA
• B
• BA
• BAA

That often makes everything click.

Final summary¶

What the program is doing:

• it builds sequences one letter at a time

Why recursion is inside the loop:

• because from one state, there are several possible next letters
• for each one, you recursively explore what happens next

Why this is DFS:

• it explores one branch fully before trying the next branch

What backtracking is here:

• choose a letter
• recurse
• restore the count

What is counted:

• every newly formed non-empty sequence

Why duplicates are avoided:

• you branch by letter type and remaining count
• not by physical tile position

If you want to really internalize it, use the path-printing version and trace "AAB" manually side by side with the tree.