问题描述
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?
问题分析
问题要求可能的组合数量，且序列顺序不同也视作不同的组合类型。
起初想法是按照硬币问题的方式，假设初始只有一个可用元素，计算组合数量；然后增加到2个元素，再计算组合数量。但是由于序列顺序不同也要考虑，因此硬币组合问题这种单纯只考虑组合方式，不考虑顺序的解决方法就行不通了。
继续分析问题，可以发现：
假设我们定义dp[i]为target等于i时的组合数量；那么如果我们固定组合序列第一位为x，则这种情况下组合数量等于 dp[i-x]; 同理，我们考虑dp[i-x]时，继续固定第一位为x，则[x,x,…]这种情况下的组合数量为 dp[i-x-x];
如果固定第一位为y, 则同上，有[y,…]组合方式为 dp[i-y]
如果画成一颗树，我们就会发现很多子树一样的；也就是说，可以分解为多个子问题。那么综上，我们可以得出结论：
对于dp[i]， 其结果等于以下子问题的和： 即sum(dp[i-nums[0]], dp[i-nums[1]], …)， 其中，i-nums[0] > 0
示例代码如下
示例代码
func combinationSum4(nums []int, target int) int {
// 先排序，方便后续处理
sort.Slice(nums, func(i, j int) bool {
return nums[i] < nums[j]
})
// dp[i]表示target为i时的组合数量
dp := make([]int, target+1)
for _, v := range nums {
// 初始化，dp[i]仅由i 这1个元素组成
if v <= target {
dp[v] = 1
}
}
// 从最小值开始遍历，直至target
for i := nums[0]; i <= target; i++ {
// 对于dp[i]，按照以下规则逐步更新
// 1. 先放置一个nums[0]元素，如果i-nums[0] > 0, 则 dp[i]的一部分等于 dp[i-nums[0]]
// 2. 同理，dp[i]的另外一部分等于 dp[i-nums[1]]
// 3. 综上，dp[i] = sum(dp[i-nums[0]], dp[i-nums[1]], ...), if i-nums[j] > 0
for j := 0; j < len(nums); j++ {
if i-nums[j] <= 0 {
break
}
dp[i] += dp[i-nums[j]]
}
}
return dp[target]
}