I have wrote a BFS solution for the problem but I don’t know how to optimize it
problem link - https://leetcode.com/problems/combination-sum-iv/
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
q = deque()
p=0
mp = defaultdict(int)
for x in nums:
if x==target:
p+=1
if x<target:
mp[x]+=1
q.append(x)
while q:
curs=q.popleft()
for x in nums:
if curs+x<=target:
if (curs+x)==target:
p+=mp[x]
continue
if (target-curs-x) in mp:
p+=mp[curs+x]
continue
mp[curs+x]+=1
q.append(curs+x)
return p