educative.io

Optimizing the solution for Combination Sum

Courses
,
#1

Two optimizations I’m thinking about: In the solution provided, we

  1. build and store our sub-solutions as lists, which can have length O(t). If we store Counters instead, could we reduce that space to O(n)?

  2. check whether the sub-solution is present in a list of lists (line 12: if temp not in dp[i]), which takes time comparing every element. Could we use hashing to reduce this to constant time? For instance, if we stored sub-solutions as tuples, they’d offer constant-time equality checks.

Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Solution: Combination Sum - Grokking Coding Interview Patterns in Python

1 Like
#2

Hello @Isaac_Haseley,

Yes, the optimizations that you’ve mentioned do affect the overall time and space complexity of the solution in a better way.

  • It efficiently manages memory and processing time by leveraging hashing and set operations to avoid duplications.
  • It scales better with large inputs or higher target values, where the number of possible combinations increases dramatically.

But since we wanted to teach the dynamic programming approach to solving this problem, thus it lies under that heading. Otherwise, it is true that there are many other ways in solving this problem, one such is the above you’ve mentioned.

#3

Hey @Dian_Us_Suqlain!

Would either of these optimizations mean we’re no longer doing dynamic programming? It seems like for both, we’d still be using a dp array to store prior solutions. If that’s the case, could they improve the complexity of the provided approach while maintaining a dp solution for the chapter?