anmolsainiii23's blog

Need space optimisation approach for the dp question and Mention the Time Complexity of the answer
By anmolsainiii23, history, 6 months ago, In English

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.

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What are the constraints for the sum and $$$a[i]$$$?

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can use a map instead of an array.

      → Reply
      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is why I asked constraints on sum the problem might ask to calculate number of ways to make negative sum.

      → Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply