educative.io

Space complexity of k-Sum Subsets

Courses
,
#1

This problem says the optimal solution works with O(1) space complexity. Can we really solve this with O(1) space complexity? This eliminates recursion and building subsets iteratively before checking them against the target.

I found the solution in another course: Find K-Sum Subsets

This solution says it’s O(1) space, but it uses a variable subsets to build the subsets iteratively. Doesn’t this require O(n) auxiliary space? The subset can have up to n items and isn’t necessarily part of the output. I’ve linked both courses and lessons below.

Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Find K-Sum Subsets

Course: Coderust: Hacking the Coding Interview - Learn Interactively
Lesson: Find K-Sum Subsets

1 Like
#2

Hello @Isaac_Haseley,

You are correct in mentioning that the solution to this problem cannot be O(1), it will at least require linear space to draft a correct solution to solve this problem. The space complexity needs to be addressed, thank you for sharing this feedback with us.

Happy learning!

1 Like