从LeetCode实战出发：整数划分的三种变体（限制重复、奇偶性、输出方案）及Python解法
从LeetCode实战出发：整数划分的三种变体（限制重复、奇偶性、输出方案）及Python解法
整数划分问题在算法面试中堪称"经典中的经典"，但真正让面试官眼前一亮的，往往是那些基础问题的变体。当你在LeetCode上刷过基础动态规划题目后，是否遇到过这些令人头疼的变种：要求划分数字不能重复？必须全为奇数？还要输出所有具体方案？本文将带你直击这三个高频变体，提供可直接套用的解题模板。
1. 基础回顾：整数划分的动态规划本质
在深入变体之前，我们需要明确经典整数划分问题的动态规划解法。给定正整数n，其划分数p(n)表示将n表示为正整数之和的方式数，其中顺序不重要（即1+2和2+1视为同一种划分）。
关键递推关系：
def integer_partition(n): dp = [0]*(n+1) dp[0] = 1 # 空划分 for num in range(1, n+1): for i in range(num, n+1): dp[i] += dp[i - num] return dp[n]这个解法的时间复杂度为O(n²)，空间复杂度O(n)。理解这个基础解法对处理变体至关重要，因为所有变体都是在此基础上的约束条件添加。
2. 变体一：限制数字重复的划分
2.1 问题分析与建模
当题目要求划分中的数字不能重复使用时（如LeetCode 377的变体），我们需要调整状态转移策略。此时问题等价于"从1到n的数字中选取若干不重复的数，使其和为n"。
关键修改点：
- 外层循环改为数字的遍历
- 内层循环需要逆序更新，避免同一数字被多次使用
2.2 Python实现
def unique_partition(n): dp = [0]*(n+1) dp[0] = 1 for num in range(1, n+1): for i in range(n, num-1, -1): # 逆序更新 dp[i] += dp[i - num] return dp[n]示例对比：
| n | 标准划分数 | 不重复划分数 |
|---|---|---|
| 4 | 5 | 2 |
| 5 | 7 | 3 |
| 6 | 11 | 4 |
3. 变体二：奇数限制划分
3.1 奇偶性约束处理
当要求划分数字必须全为奇数时，我们需要从根本上改变数字的选取策略。此时有效的加数只能是1,3,5,...等奇数。
数学洞察： 实际上，将n划分为奇数之和的方案数等于将n划分为不同数字（不必为奇数）的方案数。这是一个有趣的数学等价关系。
3.2 优化实现
def odd_partition(n): dp = [0]*(n+1) dp[0] = 1 for num in range(1, n+1, 2): # 仅遍历奇数 for i in range(num, n+1): dp[i] += dp[i - num] return dp[n]性能对比：
- 原始解法遍历n个数字
- 优化后只需遍历⌈n/2⌉个奇数
- 空间复杂度保持不变
4. 变体三：输出所有划分方案
4.1 回溯法引入
当需要输出具体划分方案时，动态规划的表记录方法不再适用，我们需要转向回溯算法。这类问题在面试中经常出现，如LeetCode 39、40等组合总和问题。
关键考虑：
- 避免重复方案（如1+2和2+1）
- 控制递归深度
- 剪枝优化
4.2 完整Python实现
def partition_solutions(n): def backtrack(target, start, path): if target == 0: res.append(path.copy()) return for num in range(start, target+1): if num > target: continue path.append(num) backtrack(target - num, num, path) # 保持start=num避免重复 path.pop() res = [] backtrack(n, 1, []) return res复杂度分析：
- 时间复杂度：O(2^n) 最坏情况
- 空间复杂度：O(n) 递归栈深度
5. 综合应用：混合约束问题
在实际面试中，问题往往会组合多个约束条件。比如"输出所有由不同奇数组成的划分方案"。这时我们需要整合前述技巧：
def unique_odd_partitions(n): def backtrack(target, start, path): if target == 0: res.append(path.copy()) return for num in range(start, target+1, 2): # 仅奇数 if num > target: continue path.append(num) backtrack(target - num, num + 2, path) # 下个奇数且不重复 path.pop() res = [] backtrack(n, 1, []) return res测试案例：
>>> unique_odd_partitions(7) [[1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 3], [1, 1, 5], [1, 3, 3], [7]]6. 面试实战技巧
当面对整数划分变体问题时，建议采用以下思考框架：
- 明确约束条件：先确定是计数问题还是方案输出问题
- 选择方法：
- 纯计数 → 动态规划
- 需要具体方案 → 回溯法
- 调整状态转移：
- 限制重复？修改遍历顺序
- 奇偶限制？过滤数字集合
- 边界处理：
- n=0时的空划分
- 起始数字的选择
常见陷阱：
- 忘记初始化dp[0]=1
- 顺序依赖导致的重复计数
- 回溯时没有正确维护起始位置
在最近的Google面试中，有候选人被要求实时编写一个输出所有划分方案的代码，面试官特别关注了回溯过程中如何避免生成重复方案的细节处理。