LeetCode 솔루션 분류

[8/5] 377. Combination Sum IV

컨텐츠 정보

본문

Medium
4676496Add to ListShare

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 <= 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?

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.
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]
LeetCode 솔루션 357 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 899 명
  • 오늘 방문자 5,688 명
  • 어제 방문자 6,932 명
  • 최대 방문자 14,831 명
  • 전체 회원수 1,481 명
알림 0