What is the core pattern used in Combination Sum IV?

The core pattern used is state transition dynamic programming, where we progressively calculate the number of ways to reach each target sum.

How does the bottom-up approach work for Combination Sum IV?

In the bottom-up approach, you calculate the number of ways to reach smaller targets first, using previously computed values to build up to the target.

What is the space complexity of the optimal solution?

The optimal solution has a space complexity of O(target), achieved by reducing the DP array to a single dimension.

How do I handle edge cases in Combination Sum IV?

Edge cases include scenarios where no combination exists for the target, in which case the result will be 0.

Can I use the same number from nums multiple times?

Yes, you can use any number from `nums` multiple times, and the order of numbers matters, so different permutations count as different combinations.

#377

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

组合总和 Ⅳ

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素排列的个数。题目数据保证答案符合 32 位整数范围。示例 1：输入： nums = [1,2,3], target = 4 输出： 7 解释：所有可能的组合…

数组动态规划

题目描述

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素排列的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3
输出：0

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i]$ 表示总和为 $i$ 的元素组合的个数，初始时 $f[0] = 1$ ，其余 $f[i] = 0$ 。最终答案即为 $f[target]$ 。

对于 $f[i]$ ，我们可以枚举数组中的每个元素 $x$ ，如果 $i \ge x$ ，则 $f[i] = f[i] + f[i - x]$ 。

最后返回 $f[target]$ 即可。

时间复杂度 $O(n \times target)$ ，空间复杂度 $O(target)$ 。其中 $n$ 为数组的长度。

1

2

3

4

5

6

7

8

9

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        f = [1] + [0] * target
        for i in range(1, target + 1):
            for x in nums:
                if i >= x:
                    f[i] += f[i - x]
        return f[target]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for familiarity with dynamic programming concepts, specifically state transition and bottom-up approaches.
question_mark
Candidates should be able to explain the transition between states clearly, showing understanding of dynamic programming.
question_mark
Candidates should also discuss space optimization techniques like reducing the DP array to a one-dimensional structure.

warning

常见陷阱

外企场景

error
Forgetting that different orders of the same combination count as distinct.
error
Incorrectly initializing or updating the DP array, leading to missing or incorrect combinations.
error
Not considering edge cases such as when `nums` has no valid combinations for the target.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Changing the problem to disallow repeated elements in combinations.
arrow_right_alt
Adding constraints where some numbers in `nums` can only be used a limited number of times.
arrow_right_alt
Using a different set of operations, such as subtraction instead of addition, and adjusting the approach accordingly.

help

常见问题

外企场景

继续练习

#376 摆动序列 #368 最大整除子集 #396 旋转函数