题目描述
思路解析动画文字版
记住这套「挑一个就算一种、走到头收回换下一个、相同字母只挑一次」，下面每一帧都在套它。
上面一排是三个字模 A、A、B（已经排好序），下面 path 是正在拼的序列，右边收集每一种印出来的序列。规矩：每层挑一个没用过的字模接到 path 末尾，接出一个就算印出一种。
挑第 0 个字模 A，接到末尾，拼出序列 "A"。每拼出一个非空序列就算印出一种，答案加到 1。
挑第 1 个字模 A，接到末尾，拼出序列 "AA"。每拼出一个非空序列就算印出一种，答案加到 2。
挑第 2 个字模 B，接到末尾，拼出序列 "AAB"。每拼出一个非空序列就算印出一种，答案加到 3。
"AAB" 这条已经拼满、把末尾的 B 收回来，path 退回 "AA"，回上一层换下一个字模。
"AA" 这条能接的都试过了，把末尾的 A 收回来，path 退回 "A"，回上一层换下一个字模。
挑第 2 个字模 B，接到末尾，拼出序列 "AB"。每拼出一个非空序列就算印出一种，答案加到 4。
挑第 1 个字模 A，接到末尾，拼出序列 "ABA"。每拼出一个非空序列就算印出一种，答案加到 5。
"ABA" 这条已经拼满、把末尾的 A 收回来，path 退回 "AB"，回上一层换下一个字模。
"AB" 这条能接的都试过了，把末尾的 B 收回来，path 退回 "A"，回上一层换下一个字模。
"A" 这条能接的都试过了，把末尾的 A 收回来，path 退回 空，回上一层换下一个字模。
这一层又遇到字母 A，它和前一个 A 一样、而且前一个这层还没挑，选它拼出来的序列会和刚才那条重复，跳过去重。
挑第 2 个字模 B，接到末尾，拼出序列 "B"。每拼出一个非空序列就算印出一种，答案加到 6。
挑第 0 个字模 A，接到末尾，拼出序列 "BA"。每拼出一个非空序列就算印出一种，答案加到 7。
挑第 1 个字模 A，接到末尾，拼出序列 "BAA"。每拼出一个非空序列就算印出一种，答案加到 8。
"BAA" 这条已经拼满、把末尾的 A 收回来，path 退回 "BA"，回上一层换下一个字模。
"BA" 这条能接的都试过了，把末尾的 A 收回来，path 退回 "B"，回上一层换下一个字模。
这一层又遇到字母 A，它和前一个 A 一样、而且前一个这层还没挑，选它拼出来的序列会和刚才那条重复，跳过去重。
"B" 这条能接的都试过了，把末尾的 B 收回来，path 退回 空，回上一层换下一个字模。
三个字模的所有挑法都搜遍了，右边正好攒了 8 种不同的非空序列：A、AA、AAB、AB、ABA、B、BA、BAA。所以 "AAB" 的答案就是 8。
小规模手算验证：单字母 1 种、两个相同 2 种、两个不同 4 种。
两个高频追问：和全排列的区别、以及可以但没必要的公式法。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def numTilePossibilities(self, tiles: str) -> int: def dfs(cnt: Counter) -> int: ans = 0 for i, x in cnt.items(): if x > 0: ans += 1 cnt[i] -= 1 ans += dfs(cnt) cnt[i] += 1 return ans cnt = Counter(tiles) return dfs(cnt)复杂度
- 时间：O(n · n!)，搜索树节点数即非空序列数，上界约 n·n!；本题 n ≤ 7 实际很小
- 空间：O(n)，递归栈深最多 n 层；计数表固定 26 个槽位视作常数
易错点
面试追问把动画讲成自己的话
追问这题和全排列（lc46/lc47）有什么区别？
追问能不能不搜索，直接用组合数学公式算？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
黄金矿工
LeetCode 1219 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题