377. 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 的排列，就能构造出无限长度的排列。如果允许负数出现，则必须限制排列的最大长度，不然会出现无限长度的排列。

代码 #

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]
	}
}