Partition to K Equal Sum Subsets - Backtracking - Leetcode 698 - Python

Problem Link: Partition to K Equal Sum Subsets

0:00 - Read the problem
3:09 - Explain Solution #1
5:42 - Explain Solution #2
9:32 - Coding Explanation

leetcode 698

#sorted #array #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[NeetCode]

Correction: The time complexity of the 2nd solution is actually O(2^ (k*n)), because if we have K trees stacked on top of each other, the new height of the tree is K * n.

[findingMyself.yearsago]

It's giving timeout for the above code, by adding minor conditions we can pass through this

since we already sorted the array, the duplicated numbers are also stuck together. We can tweak the for a loop a little bit to avoid duplicated backtracking

# Avoid duplicated backtracking
if i > 0 and not visited[i -1] and nums[i] == nums[i - 1]:
continue


Hope this helps


Full Code:

def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:

n = len(nums)
nums.sort(reverse=True)
total = sum(nums)
if total % k != 0:
return False

target = int(total / k)
used = [False] * n

def dfs(index, total, k):

if k == 0:
return True

if total == 0:
return dfs(0, target, k - 1)

for i in range(index, n):

if i > 0 and not used[i - 1] and nums[i] == nums[i - 1]:
continue

if used[i] or total - nums[i] < 0:
continue

used[i] = True
if dfs(i + 1, total - nums[i], k):
return True
used[i] = False
return False

return dfs(0, target, k)

[andreipoehlmann]

The additional optimizations in the end are a nice bonus and probably also important. I imagine they would help a lot with follow-up questions if they're not part of your initial solution.

[oooo-rcyf]

You're explanation made it seem so clear and simple. Thank you so much!

[Laura-kehr]

To fix the new TLE error change the first conditional statement in the for loop to this:

if used[j] or subsetSum + nums[j] > target or (j > 0 and nums[j] == nums[j-1] and not used[j-1]):
continue

[sauravchandra]

Finally found someone who could explain me this problem.

[Iamnoone]

I saw your post yesterday can you please make video on how to calculate time complexity of recursive problems, i am really having a hard time to calculate it

[CSBAjay]

Those who want backtracking solution with memoization.. they can refer this code....
class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
used = [False]*len(nums)
total_sum = sum(nums)
if total_sum % k != 0:
return False
target = total_sum // k
nums.sort(reverse = True)

#sorting the array in descending order
#so if first value is greater than target, it will not be included in any subset
#so we cant partition the entire array into k equal sum subsets
if nums[0] > target:
return False

dp = {}
def backtrack(i, k, rem):
#since subproblem depends on used indices of array
#if same subproblem occurs again just return dp value
if tuple(used) in dp:
return dp[tuple(used)]
if k == 0:
return True
if rem == 0:
partition = backtrack(0, k-1, target)
dp[tuple(used)] = partition
return partition
for j in range(i, len(nums)):
if not used[j] and rem-nums[j] >= 0:
used[j] = True
if backtrack(j+1, k, rem-nums[j]):
return True
used[j] = False
dp[tuple(used)] = False
return False
return backtrack(0, k, target)

[praneenderguptavuppala]

Implemented same algorithm in Java. only 53 test cases passed - Rest are failing with time limit exceeded. Looks like TC is not k * 2^n. Its 2 ^ (k*n)

[---zzzl]

I got a Time Limit Exceed by this method.... exactly the same code and I don't know why

[chennakesava]

Hey great solution.
But the tree that u drew doesn't correspond to the solution u wrote.

There are 2 recursive approaches (that is know of), for subsets using recursion
1. take/don't take approach (classical)
2. brute force dfs approach (dfs)

the tree u drew is of "take/don't take approach" but u coded it in "dfs approach"

[VarunMittal-viralmutant]

I think this question is the same as "matchsticks to square" question with a twist that instead of just 4 we can have k partitions. And that is the O(N ^ K) solution that you mention at the beginning. It passes 151/159 test cases before running into TLE

[madhukiranattivilli]

2 points -- a problem, a suggestion.

Problem

You suggested to sort numbers in desc order to speed up the algo. I notice, if not desc sorted, algo may sometimes give correct result based on incorrect data (non-disjoint subsets), or may give incorrect result.

For instance, if sorted -- 1 2 2 3 3 4 5 -- subsets would be (1 2 2), (5), (1 4), (2 3). Numbers 1 and 2 are part of multiple subsets. Yet algo returns true. But data is not as per expectations.

So, desc sort is a mandatory requirement -- 5 4 3 3 2 2 1. Subsets would be (5) (4 1) (3 2) (3 2)

If not done, 2nd best solution could be :
Let the recursive algo run until all combinations of numbers are examined -- i.e. remove the (k == 0) check. Collect all subsets of numbers, possibly non-disjoint. For numbers 1 2 2 3 3 4 5 we would get non-disjoint subsets (1 2 2) (5) (1 4) (2 3) (2 3) (2 3) (2 3) -- 7 subsets. Now, repeat the same recursive algo on the subsets. In 1st run, input is the list of numbers, and we sum the numbers, and add to a subset when they add up to the subset size. In 2nd run, input is the list of subsets, and we reject non-disjoint subsets. When algo ends, we would've <= k disjoint subsets.

SUGGESTION

We can add one more check -- Exit program if any of the numbers is > subset size (subset size = sumOfNumbers/k)

Please comment

[DJ-vxgl]

Note, seems they've added new test cases so this backtracking solution without memoization will cause TLE.

[srikanthvelpuri]

Keep doing more videos bro...I always loved your explanation and I am preparing for job interviews...I will let you know if I get a job...Please keep making such good content for free.

[Opportunity]

A lot of people said this solution TLE. Today is March 2022, I used the same code in Javascript, passed all cases. Runtimes are varying for the same solution (3-7seconds), I guess it depends on the speed of the provider. Neetcode - thank you so much for all these videos! You make it simpler to understand for a ton of people!

[ChanChan-pgwu]

Great explanation! This one is very similar to LC#473 but more complicated.

[mmaximov]

Backtracking without memoization doesn't work in leetcode anymore

[deathstrokebrucewayne]

One doubt - Since we have 2 choices at every backtracking step - Include or dont iclude the current element - Why haven't we done this:
``` if backtrack(j+1, k, subsetSum + nums[j]) or backtrack(j+1, k, subsetSum): ```

Do we never look into this path - backtrack(j+1, k, subsetSum)?
@neetCode

[rahulnegi]

Getting TLE, need to add one more check of skipping duplicates