You are given an array of n elements and a sum value, you have to calculate the total number of ways to calculate the given sum using the elements of the array by using only addition(+) and subtraction operator(-).
Value of n should lie between [1,15]
array => [-1, 9, 8, -3, 4] value sum => 5
Output -: 8
I have applied Recursion and Memo also but I want a space Optimization Approach for this Question. Please Explain the Working and Time Complexity of this Code and share the Code snippet.
What are the constraints for the sum and $$$a[i]$$$?
That is not specifically not mentioned but the value in array will lie from 1 to 15. so you can take the constraint by your choice and give me an answer and one more thing if I will make a dp[index][sum] array then sum can also be negative then how you will deal with that?
You can use a map instead of an array.
Can you just give me a solution with the map also. what I did was to just hit base condition and rather storing dp[index][sum] I stored dp[index][sum+target] so that Might Work.
This is why I asked constraints on sum the problem might ask to calculate number of ways to make negative sum.
I think if you want to optimise space what you can use is a state $$$dp[sum]$$$. Now since the size of the array is in the range $$$n\in$$$ $$$[1, 15]$$$. You can have $$$2^n$$$ possible arrays (since each element have two choices either be positive or negative). Now for all these arrays you can apply subset sum dp. So overall time complexity will be $$$2^n$$$ * $$$n$$$ * $$$sum$$$ and space will be $$$O(sum).$$$ I'm assuming problem does not ask us to form negative sum, If it does then you can use map.
No. You can choose to pick and not pick. So if you will pick then you have two choices. So in general we have three choices. That is Pick with + and Pick with — and Not Pick. That is the actual thing. I am using dp[index][sum + target] and added a base condition. The output is coming for the required testcase.
This is basically subset sum problem, Each number have two choices either + or -, i guess i have solved this problem on leetcode too, but unable to remember the exact name of the problem.