暴力枚举基本功
🔖 #46 · Permutations ★
难度: Medium | 标签: Backtracking | 链接: https://leetcode.com/problems/permutations/
题目描述
给定不含重复数字的数组，返回其所有可能的全排列。
解题思路
回溯模板：维护
path，递归选择尚未使用的元素。答案代码
def permute(nums): res = [] def bt(path, remaining): if not remaining: res.append(path[:]) return for i, n in enumerate(remaining): path.append(n) bt(path, remaining[:i] + remaining[i+1:]) path.pop() bt([], nums) return res
扩展总结
- 回溯公共模板：选择 → 递归 → 撤销
- #47 Permutations II：包含重复元素，需要排序后跳过重复
🔖 #22 · Generate Parentheses ★
难度: Medium | 标签: Backtracking | 链接: https://leetcode.com/problems/generate-parentheses/
题目描述
生成所有包含 n 对括号的有效组合。
解题思路
递归维护 open 和 close 的数量：如果 open < n，可加 '('；如果 close < open，可加 ')'。
答案代码
def generateParenthesis(n): res = [] def bt(path, open, close): if len(path) == 2 * n: res.append(path) return if open < n: bt(path + '(', open + 1, close) if close < open: bt(path + ')', open, close + 1) bt('', 0, 0) return res
扩展总结
- 经典题，考察对合法条件的理解
- 提前剪枝（pruning）使回溯更高效
🔖 #5 · Longest Palindromic Substring
难度: Medium | 标签: String, DP | 链接: https://leetcode.com/problems/longest-palindromic-substring/
题目描述
给定字符串 s，返回最长回文子串。
解题思路
中心扩展：对每个中心（奇数和偶数长度）尝试向外扩展。O(n²) 时间，O(1) 空间。
答案代码
def longestPalindrome(s): res = "" def expand(l, r): while l >= 0 and r < len(s) and s[l] == s[r]: l -= 1; r += 1 return s[l+1:r] for i in range(len(s)): for p in [expand(i, i), expand(i, i+1)]: if len(p) > len(res): res = p return res
扩展总结
- Manacher 算法可到达 O(n)，但实际面试中中心扩展已够
- #647 Palindromic Substrings — 计算回文子串总数
🔖 #78 · Subsets
难度: Medium | 标签: Backtracking, Bit | 链接: https://leetcode.com/problems/subsets/
题目描述
返回子集。
答案代码
def subsets(nums): res = [] def bt(start, path): res.append(path[:]) for i in range(start, len(nums)): path.append(nums[i]) bt(i + 1, path) path.pop() bt(0, []) return res
扩展总结
- 也可用位操作：2ⁿ 种子集，用二进制位表示
- #90 Subsets II：包含重复，需排序和剪枝