p377

发表于 | 分类于 |

LeetCode 377 Combination Sum IV 题解

1.题目：

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
nums = [1, 2, 3]
target = 4
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.
Therefore the output is 7.

题意：

输入一个数组，和一个目标值，写出这个目标值有多少种合成方式。

2.解题思路:

用DP。借鉴了大神们的写法~代码瞬间优雅了起来~
便利出所有比目标值小的数的组合方式。一层一层往上累加。
关键等式是a[i] += a[i - num]; 设k=i-num.则 i=k+num.
此时正遍历到num,所以将num作为定值，将a[i]原来的组合方式累加上num+k这种方式，假设num不变，即为k的可替代方式。
所以a[i] += a[i - num]成立。
还有一点附加的~如果数组内刚好有值与 目标值相等。。算不算一种呢~感觉应该不算加法~不过测试用例好像也没有卡这个边界~。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        if (nums.length < 2)
			return 0;
		int[] a = new int[target + 1];
		Arrays.sort(nums);
		a[0] = 1;
		for (int i = 0; i < target + 1; i++) {
			for (int num : nums) {
				if (num <= i) {
					a[i] += a[i - num];
				} else {
					break;
				}
			}
		}
		return a[target];
    }
}

4.一些总结：