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.
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.