educative.io

https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews/3jEPRo5PDvx

Courses
,
#1 
#WindowEnd works out of for loop because of loop_variable leakage in Python
def equal_subset(num):
     windowStart = 0
     _sum = 0
     half = sum(num)/2
     for windowEnd in range(len(num)):
           _sum += num[windowEnd]
           do_break = False
           while _sum > half
               _sum -= num[windowStart]
               windowStart += 1
               if _sum == half:
                   do_break = True
                   break
           if do_break:break
     first_set = sum(num[windowStart:windowEnd+1])
     second_set = sum(num[0:windowStart] + num[windowEnd+1:])
     if not first_set == second_set:
          return False
     return True

I have a solution with O(N) Time complexity and O(1) space Complexity

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5633779737559040
Lesson: https://www.educative.io/collection/page/5668639101419520/5633779737559040/5752754626625536

#2

Dear @learn,
I have tried running the code. It has a syntax error. Please add “:” in line 8, after while _sum > half. Correct code is:

def equal_subset(num):
 windowStart = 0
 _sum = 0
 half = sum(num)/2
 for windowEnd in range(len(num)):
       _sum += num[windowEnd]
       do_break = False
       while _sum > half:
           _sum -= num[windowStart]
           windowStart += 1
           if _sum == half:
               do_break = True
               break
       if do_break:break
 first_set = sum(num[windowStart:windowEnd+1])
 second_set = sum(num[0:windowStart] + num[windowEnd+1:])
 if not first_set == second_set:
      return False
 return True

It runs fine. I hope it helps!

#3

Thanks @Tehreem_Arshad for correcting the syntax.
And I am sorry for being vague in my question.
The solution I have provided for “Equal Subset Sum Partition” is having O(N) time complexity and O(1) Space complexity. which is less than the given solution in the course.
Inshort: No memoization and no nested loops.
The above one is an implementation of sliding window pattern.
Incase if a question arises why O(N) for this sliding Window pattern then the “while loop” doesn’t run for every iteration of the outer(for) loop.