377. Combination Sum IV #

Problem #

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?

Problem Summary #

Given an array nums composed of distinct integers and a target integer target. Find and return the number of element combinations from nums whose sum is target. The problem data guarantees that the answer fits within the 32-bit integer range.

Solution Approach #

Combination Sum is a series of problems. After getting this problem, I first tried a brute-force dfs solution, but it contained many overlapping subproblems and the pruning conditions were not written well, so unsurprisingly it timed out. There are only the three elements [1,2,3], and target = 32, yet this set of data actually has as many as 181997601 cases. Looking carefully at the data scale of 1000, it can basically be determined that this problem should use dynamic programming, and the time complexity is O(n^2).
This problem is somewhat similar to the complete knapsack problem, but there are still differences. In complete knapsack, the order within a selection is not distinguished. For example, 5 = 1 + 2 + 2. But in this problem there are 3 answers: (1, 2, 2), (2, 1, 2), (2, 2, 1). Define dp[i] as the total number of combinations whose sum is target = i. The final answer is stored in dp[target]. The state transition equation is:
\[ dp[i] =\left\{\begin{matrix}1,i=0\\ \sum dp[i-j],i\neq 0\end{matrix}\right. \]
This problem has a follow-up question at the end. If the given array contains negative numbers, it will lead to permutations of infinite length. For example, suppose the array nums contains a positive integer a and a negative integer −b (where a>0,b>0,-b<0), then a×b+(−b)×a=0. For any permutation whose element sum equals target, after appending b copies of a and a copies of −b to the end of that permutation, the sum of the elements in the new permutation still equals target, and we can continue appending b copies of a and a copies of −b to the end of the new permutation. Therefore, as long as there exists a permutation whose element sum equals target, permutations of infinite length can be constructed. If negative numbers are allowed, the maximum length of the permutation must be limited; otherwise, permutations of infinite length will occur.

Code #

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

// Brute-force solution times out
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]
	}
}