0377. Combination Sum I V

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

⬅️上一页

下一页➡️

Calendar Jun 16, 2021
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者