Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 377 with 15 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 377 # by problem number
lcpy gen -s combination_sum_iv # by problem name
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.
Note that different sequences are counted as different combinations.
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.
Input: nums = [9], target = 3
Output: 0
nums are unique.class Solution:
# Bottom-up DP: dp[t] = number of ways to reach sum t
# dp[t] = sum(dp[t - num] for num in nums if t >= num), dp[0] = 1
# Order matters, so iterate target outer, nums inner
# Time: O(target * n)
# Space: O(target)
def combination_sum4(self, nums: list[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
for t in range(1, target + 1):
for num in nums:
if t >= num:
dp[t] += dp[t - num]
return dp[target]
| Time | Space |
|---|---|
| O(target * n) | O(target) |