题目描述
思路解析动画文字版
记住一句：dp[t] 把「最后一步选谁」全枚举一遍，每个选择把对应 dp[t−num] 加进来。
边界：先填边界：凑出和 0，只有"一个数都不选"这一种 → dp[0]=1。
dp[1] 来路·选 1：凑和 1：最后一个数选 1，剩下要凑 0 → 把 dp[0]=1 加进来。
落子 dp[1]=1：1 条来路全加完：dp[1] = 1。
dp[2] 来路·选 1：凑和 2：最后一个数选 1，剩下要凑 1 → 把 dp[1]=1 加进来。
dp[2] 来路·选 2：凑和 2：最后一个数选 2，剩下要凑 0 → 把 dp[0]=1 加进来。
落子 dp[2]=2：2 条来路全加完：dp[2] = 2。
dp[3] 来路·选 1：凑和 3：最后一个数选 1，剩下要凑 2 → 把 dp[2]=2 加进来。
dp[3] 来路·选 2：凑和 3：最后一个数选 2，剩下要凑 1 → 把 dp[1]=1 加进来。
dp[3] 来路·选 3：凑和 3：最后一个数选 3，剩下要凑 0 → 把 dp[0]=1 加进来。
落子 dp[3]=4：3 条来路全加完：dp[3] = 4。
dp[4] 来路·选 1：凑和 4：最后一个数选 1，剩下要凑 3 → 把 dp[3]=4 加进来。
dp[4] 来路·选 2：凑和 4：最后一个数选 2，剩下要凑 2 → 把 dp[2]=2 加进来。
dp[4] 来路·选 3：凑和 4：最后一个数选 3，剩下要凑 1 → 把 dp[1]=1 加进来。
落子 dp[4]=7：3 条来路全加完：dp[4] = 7。
dp[5] 来路·选 1：凑和 5：最后一个数选 1，剩下要凑 4 → 把 dp[4]=7 加进来。
dp[5] 来路·选 2：凑和 5：最后一个数选 2，剩下要凑 3 → 把 dp[3]=4 加进来。
dp[5] 来路·选 3：凑和 5：最后一个数选 3，剩下要凑 2 → 把 dp[2]=2 加进来。
落子 dp[5]=13：3 条来路全加完：dp[5] = 13。
dp[6] 来路·选 1：凑和 6：最后一个数选 1，剩下要凑 5 → 把 dp[5]=13 加进来。
dp[6] 来路·选 2：凑和 6：最后一个数选 2，剩下要凑 4 → 把 dp[4]=7 加进来。
dp[6] 来路·选 3：凑和 6：最后一个数选 3，剩下要凑 3 → 把 dp[3]=4 加进来。
落子 dp[6]=24：3 条来路全加完：dp[6] = 24。
答案：dp[6]=24 就是凑出 6 的全部组合数。一维 DP 一遍扫完，O(target × nums) 搞定。
边界三连：凑不出时不是报错，而是自然得 0——因为没有任何 num 能落进 dp[t] 的累加，那一格保持初始的 0。
面试追问：把「为什么是排列」「负数为何失效」「与完全背包的循环顺序关系」讲清，是这题最容易被追问的三点。
参考代码
class Solution: def combinationSum4(self, nums, target): dp = [0] * (target + 1) dp[0] = 1 # 凑出 0 有空方案这一种 for t in range(1, target + 1): # 外层:总和 t for num in nums: # 内层:最后取哪个 num if num <= t: dp[t] += dp[t - num] # 累加 dp[t-num] return dp[target]复杂度
- 时间复杂度：O(target × n)，每个总和 t 都扫一遍 nums(n 个数)，共 target 个总和
- 空间复杂度：O(target)，一维 dp 数组，长度 target+1
易错点
面试追问把动画讲成自己的话
追问题目叫「组合」，为什么算的是排列？
追问如果 nums 含负数会怎样？
追问和完全背包求方案数有什么联系？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
零钱兑换 II
LeetCode 518 · 中等 · 沿着 完全背包套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题