组合总和 Ⅳ 图解题解

这道题到底在问什么

输入

nums = [1,2,3], target = 6

输出

24

先想最直接的笨办法

记住一句：dp[t] 把「最后一步选谁」全枚举一遍，每个选择把对应 dp[t−num] 加进来。（动画第 3 步）

最优解：一步一步想明白

1. 3记住一句：dp[t] 把「最后一步选谁」全枚举一遍，每个选择把对应 dp[t−num] 加进来。
2. 4dp[0]=1先填边界：凑出和 0，只有"一个数都不选"这一种 → dp[0]=1。
3. 5凑和 1：最后一个数选 1，剩下要凑 0 → 把 dp[0]=1 加进来。
4. 61 条来路全加完：dp[1] = 1。
5. 7凑和 2：最后一个数选 1，剩下要凑 1 → 把 dp[1]=1 加进来。
6. 8凑和 2：最后一个数选 2，剩下要凑 0 → 把 dp[0]=1 加进来。
7. 92 条来路全加完：dp[2] = 2。
8. 10凑和 3：最后一个数选 1，剩下要凑 2 → 把 dp[2]=2 加进来。
9. 11凑和 3：最后一个数选 2，剩下要凑 1 → 把 dp[1]=1 加进来。
10. 12凑和 3：最后一个数选 3，剩下要凑 0 → 把 dp[0]=1 加进来。
11. 133 条来路全加完：dp[3] = 4。
12. 14凑和 4：最后一个数选 1，剩下要凑 3 → 把 dp[3]=4 加进来。
13. 15凑和 4：最后一个数选 2，剩下要凑 2 → 把 dp[2]=2 加进来。
14. 16凑和 4：最后一个数选 3，剩下要凑 1 → 把 dp[1]=1 加进来。
15. 173 条来路全加完：dp[4] = 7。
16. 18凑和 5：最后一个数选 1，剩下要凑 4 → 把 dp[4]=7 加进来。
17. 19凑和 5：最后一个数选 2，剩下要凑 3 → 把 dp[3]=4 加进来。
18. 20凑和 5：最后一个数选 3，剩下要凑 2 → 把 dp[2]=2 加进来。
19. 213 条来路全加完：dp[5] = 13。
20. 22凑和 6：最后一个数选 1，剩下要凑 5 → 把 dp[5]=13 加进来。
21. 23凑和 6：最后一个数选 2，剩下要凑 4 → 把 dp[4]=7 加进来。
22. 24凑和 6：最后一个数选 3，剩下要凑 3 → 把 dp[3]=4 加进来。
23. 253 条来路全加完：dp[6] = 24。
24. 26dp[6]=24dp[6]=24 就是凑出 6 的全部组合数。一维 DP 一遍扫完，O(target × nums) 搞定。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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]

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned long long> dp(target + 1, 0);
        dp[0] = 1;                       // 空方案
        for (int t = 1; t <= target; t++) {       // 外层:总和
            for (int num : nums) {                // 内层:末尾数
                if (num <= t) dp[t] += dp[t - num];
            }
        }
        return (int) dp[target];
    }
};

class Solution {
    public int combinationSum4(int[] nums, int target) {
        long[] dp = new long[target + 1];
        dp[0] = 1;                       // 空方案
        for (int t = 1; t <= target; t++) {       // 外层:总和
            for (int num : nums) {                // 内层:末尾数
                if (num <= t) dp[t] += dp[t - num];
            }
        }
        return (int) dp[target];
    }
}

复杂度

面试官可能追问