Leetcode - Combination Sum IV (Python)

April 2021 Leetcode Challenge
Leetcode - Leetcode - Combination Sum IV (Python) #377
Difficulty: Medium

[curiousMe]

Thanks for the video, bro, your explanation is not clear after 2:06.
The coding part is very intuitive but explanation of solution isnt

[janmichaelaustria]

I actually solved this recursively, but in a weird way. I thought of like building up the list, the only kicker is that you need to be careful of when and how to recurse:

class Solution(object):
def combinationSum4(self, nums, target):
memo = {}
def rec(idx, target):
count = 0
#careful not to keep going after target diminishes
if target <= 0:
if target == 0:
#valid path
return 1
return 0
if (idx, target) in memo:
return memo[(idx, target)]
for i in range(idx, len(nums)):
candidate = nums[i]
if target - candidate > 0:
#stay on the index
count += rec(idx, target-candidate)
else:
#move up the index
count += rec(idx+1, target-candidate)
memo[(idx, target)] = count
return count
return rec(0, target)

I still have a hard time trying to link the top down recursive to the bottom up iterative for problems. But I do remember you covering an earlier version of this problem months ago and sorta remembered the dp solution. XD

[xiangliangmeng]

My first impression is that this problem is a backtracking problem instead of a DP one, until my code hit the time limit for the test case [1, 2, 3] & 32. How do you know it is not a backtracking problem? Thanks.