0

I was solving target sum problem on leetcode which asks us to use either +/- symbol on all integers and then check sum of array is equal to target. I'm trying to return all possible combinations using this symbols using recursion This is my current code which works but is not optimized

nums=[1,1,1]
res=[]
def recursion(i,temp,res):
    if i==len(nums):
        res.append(temp[:])
        return
    temp.append(nums[i])
    recursion(i+1,temp,res)
    temp.pop()
    temp.append(-1*nums[i])
    recursion(i+1,temp,res)
    temp.pop()
recursion(0,[],res)
print(res)

Result of this program is: [[1, 1, 1], [1, 1, -1], [1, -1, 1], [1, -1, -1], [-1, 1, 1], [-1, 1, -1], [-1, -1, 1], [-1, -1, -1]] Can someone please help me to understand how can I memoize it?

funnydman
  • 9,083
  • 4
  • 40
  • 55
Amey-K27
  • 1
  • 1
  • There is already a good explanation on Stackoverflow: https://stackoverflow.com/questions/1988804/what-is-memoization-and-how-can-i-use-it-in-python – Philipp Gebhard Oct 10 '22 at 13:37
  • I know how to use memoization but I have not seen any problem where you need to store list of list as value pair for key. Any direction on this will be helpful – Amey-K27 Oct 10 '22 at 14:09
  • For this kind of problem, you don't need to generate all possible combinations but count those that form the target sum. – funnydman Oct 10 '22 at 14:44

0 Answers0