엔지니어 게시판
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]
전체 175 / 1 페이지
게시글 쓰기
번호
제목
이름

최근글


새댓글


Stats


  • 현재 접속자 98 명
  • 오늘 방문자 844 명
  • 어제 방문자 858 명
  • 최대 방문자 1,338 명
  • 전체 회원수 315 명
알림 0