Combination sum IV#
Practice Link#
Description#
- 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#
text
1nums = [1, 2, 3]
2target = 4
3
4The possible combination ways are:
5(1, 1, 1, 1)
6(1, 1, 2)
7(1, 2, 1)
8(1, 3)
9(2, 1, 1)
10(2, 2)
11(3, 1)
12
13Note that different sequences are counted as different combinations.
14
15Therefore the output is 7.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?
Python Solution#
py
1class Solution(object):
2 def combinationSum4(self, nums, target):
3 nums, combs = sorted(nums), [1] + [0] * (target)
4 for i in range(target + 1):
5 for num in nums:
6 if num > i: break
7 if num == i: combs[i] += 1
8 if num < i: combs[i] += combs[i - num]
9 return combs[target]