파이썬에서 합이 k가 되는 고유한 조합의 수를 찾는 프로그램

<시간/>

nums라고 하는 고유한 숫자 목록과 또 다른 숫자 k가 있다고 가정하면 합이 k가 되는 고유한 조합의 수를 찾아야 합니다. 조합을 만들 때 숫자를 재사용할 수 있습니다.

따라서 입력이 nums =[2, 4, 5] k =4와 같으면 [2, 2] 및 [4]와 같은 두 그룹을 만들 수 있으므로 출력은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

table :=크기가 k + 1이고 0으로 채워진 목록
테이블[0] :=1
숫자 단위의 각 숫자에 대해 다음을 수행합니다.
- num ~ k 범위의 i에 대해
  - 테이블[i] :=테이블[i] + 테이블[i - 숫자]
반환 테이블[k]

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시 코드

class Solution:
   def solve(self, nums, k):
      table = [1] + [0] * k

      for num in nums:
         for i in range(num, k + 1):
            table[i] += table[i - num]

         return table[k]

ob = Solution()
nums = [2, 4, 5]
k = 4
print(ob.solve(nums, k))

입력

[2, 4, 5], 4