Description#
Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.
The test cases are generated so that the answer can 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 <= 2001 <= 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?
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
| class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
f = [1] + [0] * target
for i in range(1, target + 1):
for x in nums:
if i >= x:
f[i] += f[i - x]
return f[target]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int combinationSum4(int[] nums, int target) {
int[] f = new int[target + 1];
f[0] = 1;
for (int i = 1; i <= target; ++i) {
for (int x : nums) {
if (i >= x) {
f[i] += f[i - x];
}
}
}
return f[target];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
int f[target + 1];
memset(f, 0, sizeof(f));
f[0] = 1;
for (int i = 1; i <= target; ++i) {
for (int x : nums) {
if (i >= x && f[i - x] < INT_MAX - f[i]) {
f[i] += f[i - x];
}
}
}
return f[target];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
| func combinationSum4(nums []int, target int) int {
f := make([]int, target+1)
f[0] = 1
for i := 1; i <= target; i++ {
for _, x := range nums {
if i >= x {
f[i] += f[i-x]
}
}
}
return f[target]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| function combinationSum4(nums: number[], target: number): number {
const f: number[] = new Array(target + 1).fill(0);
f[0] = 1;
for (let i = 1; i <= target; ++i) {
for (const x of nums) {
if (i >= x) {
f[i] += f[i - x];
}
}
}
return f[target];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| /**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var combinationSum4 = function (nums, target) {
const f = new Array(target + 1).fill(0);
f[0] = 1;
for (let i = 1; i <= target; ++i) {
for (const x of nums) {
if (i >= x) {
f[i] += f[i - x];
}
}
}
return f[target];
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class Solution {
public int CombinationSum4(int[] nums, int target) {
int[] f = new int[target + 1];
f[0] = 1;
for (int i = 1; i <= target; ++i) {
foreach (int x in nums) {
if (i >= x) {
f[i] += f[i - x];
}
}
}
return f[target];
}
}
|
