LeetCode 솔루션 분류
[8/5] 377. Combination Sum IV
본문
Medium
4676496Add to ListShareGiven 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
numsare 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?
Accepted
298,349
Submissions
582,623
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 84 ms, faster than 17.41% of Python3 online submissions for Combination Sum IV.
Memory Usage: 13.9 MB, less than 80.97% of Python3 online submissions for Combination Sum IV.
Memory Usage: 13.9 MB, less than 80.97% of Python3 online submissions for Combination Sum IV.
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target+1)
dp[0]=1
for i in range(target+1):
for num in nums:
if i - num >= 0:
dp[i]+=dp[i-num]
return dp[-1]
