[FEATURE REQUEST] Optimized approach to Subset Sum problem

[Rupa-Rd]

What would you like to Propose?

I would like to propose an space optimized solution to the Subset Sum problem.

Issue details

The existing subset sum problem solution's space complexity is O(n*sum). By optimizing the algorithm/ approach further, we can achieve the space complexity of O(sum) which is more efficient than the existing one.

Algorithm link: https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/SubsetSum.java

Additional Information

No response

[ssugam10]

kindly assign this issue to me

[Pranjul2002]

please assign this task to me. It will surely help you. I will do my best.

[aayu5hgit]

Hey @Rupa-Rd

I'd like to propose a solution for this:

We can reduce the space complexity by using a 1D array instead of a 2D array. Since, at any point in the iteration, the result only depends on the current row and the previous row in the matrix. Therefore, we can maintain a single row and update it in reverse order (to avoid overwriting values).

Let me know if this works, I'm implementing this on my local machine until then :)

[lfcbird]

Please assign to me.