mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 16:36:41 +08:00
98 lines
3.3 KiB
Markdown
98 lines
3.3 KiB
Markdown
# [377. Combination Sum IV](https://leetcode.com/problems/combination-sum-iv/)
|
||
|
||
|
||
## 题目
|
||
|
||
Given an array of **distinct** integers `nums` and a target integer `target`, return *the number of possible combinations that add up to* `target`.
|
||
|
||
The answer is **guaranteed** to fit in a **32-bit** integer.
|
||
|
||
**Example 1:**
|
||
|
||
```
|
||
Input: nums = [1,2,3], target = 4
|
||
Output: 7
|
||
Explanation:
|
||
The possible combination ways are:
|
||
(1, 1, 1, 1)
|
||
(1, 1, 2)
|
||
(1, 2, 1)
|
||
(1, 3)
|
||
(2, 1, 1)
|
||
(2, 2)
|
||
(3, 1)
|
||
Note that different sequences are counted as different combinations.
|
||
|
||
```
|
||
|
||
**Example 2:**
|
||
|
||
```
|
||
Input: nums = [9], target = 3
|
||
Output: 0
|
||
```
|
||
|
||
**Constraints:**
|
||
|
||
- `1 <= nums.length <= 200`
|
||
- `1 <= nums[i] <= 1000`
|
||
- All the elements of `nums` are **unique**.
|
||
- `1 <= target <= 1000`
|
||
|
||
**Follow up:** What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?
|
||
|
||
## 题目大意
|
||
|
||
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。题目数据保证答案符合 32 位整数范围。
|
||
|
||
## 解题思路
|
||
|
||
- Combination Sum 这是系列问题。拿到题目，笔者先用暴力解法 dfs 尝试了一版，包含的重叠子问题特别多，剪枝条件也没有写好，果然超时。元素只有 [1,2,3] 这三种，target = 32，这组数据居然有 181997601 这么多种情况。仔细看了题目数据规模 1000，基本可以断定此题是动态规划，并且时间复杂度是 O(n^2)。
|
||
- 本题和完全背包有点像，但是还是有区别。完全背包的取法内部不区分顺序。例如 5 = 1 + 2 + 2。但是本题是 3 种答案 (1，2，2)，(2，1，2)，(2，2，1)。定义 dp[i] 为总和为 target = i 的组合总数。最终答案存在 dp[target] 中。状态转移方程为：
|
||
|
||
$$dp[i] =\left\{\begin{matrix}1,i=0\\ \sum dp[i-j],i\neq 0\end{matrix}\right.$$
|
||
|
||
- 这道题最后有一个进阶问题。如果给定的数组中含有负数，则会导致出现无限长度的排列。例如，假设数组 nums 中含有正整数 a 和负整数 −b（其中 a>0,b>0,-b<0），则有 a×b+(−b)×a=0，对于任意一个元素之和等于 target 的排列，在该排列的后面添加 b 个 a 和 a 个 −b 之后，得到的新排列的元素之和仍然等于 target，而且还可以在新排列的后面继续 b 个 a 和 a 个 −b。因此只要存在元素之和等于 target 的排列，就能构造出无限长度的排列。如果允许负数出现，则必须限制排列的最大长度，不然会出现无限长度的排列。
|
||
|
||
## 代码
|
||
|
||
```go
|
||
package leetcode
|
||
|
||
func combinationSum4(nums []int, target int) int {
|
||
dp := make([]int, target+1)
|
||
dp[0] = 1
|
||
for i := 1; i <= target; i++ {
|
||
for _, num := range nums {
|
||
if i-num >= 0 {
|
||
dp[i] += dp[i-num]
|
||
}
|
||
}
|
||
}
|
||
return dp[target]
|
||
}
|
||
|
||
// 暴力解法超时
|
||
func combinationSum41(nums []int, target int) int {
|
||
if len(nums) == 0 {
|
||
return 0
|
||
}
|
||
c, res := []int{}, 0
|
||
findcombinationSum4(nums, target, 0, c, &res)
|
||
return res
|
||
}
|
||
|
||
func findcombinationSum4(nums []int, target, index int, c []int, res *int) {
|
||
if target <= 0 {
|
||
if target == 0 {
|
||
*res++
|
||
}
|
||
return
|
||
}
|
||
for i := 0; i < len(nums); i++ {
|
||
c = append(c, nums[i])
|
||
findcombinationSum4(nums, target-nums[i], i, c, res)
|
||
c = c[:len(c)-1]
|
||
}
|
||
}
|
||
``` |