Find Number of Distinct Combinations That Sum Up to K in Python

Suppose we have a list of distinct numbers called nums and another number k, we have to find the number of distinct combinations that sum up to k. You can reuse numbers when creating combinations.

So, if the input is like nums = [2, 4, 5] k = 4, then the output will be 2, as we can make two such groups like [2, 2] and [4].

To solve this, we will follow these steps:

• table := a list with size k + 1, and fill with 0
• table[0] := 1
• for each num in nums, do
  • for i in range num to k, do
    • table[i] := table[i] + table[i - num]
• return table[k]

Let us see the following implementation to get better understanding:

Example Code

Live Demo

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))

Input

[2, 4, 5], 4

Output

2