Partition To K Equal Sum Subsets Leetcode Problem 698 [Python Solution]

Welcome to another coding session!

Today, we're going to tackle the LeetCode problem known as Partition To K Equal Sum Subsets This problem falls under the category of backtracking and can be quite challenging.

Our goal is to determine whether it's possible to divide an integer array into k non-empty subsets, each with the same sum.

Here's the problem statement:

Problem: Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

To illustrate, let's consider an example:

Example

Input:

nums = [4, 3, 2, 3, 5, 2, 1]
k = 4


Output:

true


Explanation: It is possible to divide the array into 4 subsets: [5], [1, 4], [2, 3], and [2, 3], all with equal sums.

This problem involves making decisions at each step, and the most efficient way to solve it is through backtracking.

We'll explore two approaches: one that has a time complexity of k^n and another, more efficient approach with a time complexity of 2^n.

Let's dive into the details.

Problem Overview

The problem can be framed as follows:

1. We need to divide the nums array into k subsets.
2. The sum of each subset should be equal, which means the sum of all elements in nums divided by k.

Example 1:

Let's work through the first example to understand the problem better.

Given nums = [4, 3, 2, 3, 5, 2, 1] and k = 4, we need to check if we can create four subsets with equal sums.

In this case, the sum of all elements is 20, and when divided by k, each subset should have a sum of 5.

Here's one possible way to divide the array:
– Subset 1: [5]
– Subset 2: [1, 4]
– Subset 3: [2, 3]
– Subset 4: [2, 3]

All four subsets have equal sums of 5, so we return true.

Understanding Constraints

Before we delve into the solutions, let's understand the constraints of the problem:

• 1 <= k <= nums.length <= 16: This tells us that we can have at most 16 elements in the nums array and at most 16 partitions (subsets).

The upper limit of 16 is manageable for our backtracking solutions.
– 1 <= nums[i] <= 104: Each element in the array nums is between 1 and 10,000.

This provides us with an idea of the range of input values.
– The frequency of each element is in the range [1, 4]: Each element can appear between 1 and 4 times in the array.

This constraint gives us insight into the nature of the input data.

Now, let's explore two approaches to solving this problem: a less efficient one and a more efficient one.

Less Efficient Approach (Backtracking)

We'll start with a backtracking approach, even though it has a less favorable time complexity.

The time complexity of this approach is k^n, which is manageable for the given constraints but may not be efficient for larger inputs.

Pseudocode for the Less Efficient Approach

Let's outline our approach in pseudocode:

1. Calculate the target sum by dividing the sum of all elements in nums by k.
2. Initialize a set visited to keep track of the indices of elements that have been visited.
3. Define a recursive function, backtrack(idx, count, currSum), that will explore all possible combinations:
   • idx is the current index in nums.
   • count is the number of subsets we've successfully formed.
   • currSum is the sum of the current subset we're building.
4. Inside the backtrack function:
   • If count is equal to k, return True since we've successfully formed all subsets.
   • If currSum is equal to the target, call backtrack(0, count + 1, 0) to start building the next subset.
   • Iterate over the elements in nums from the current index idx:
     • Skip duplicates if the previous element was also skipped.
     • Check if the current element at index i is in visited or if adding it to currSum would exceed the target.

If so, skip it.
– Add the index i to visited.
– Recursively call backtrack(i + 1, count, currSum + nums[i]).
– Remove the index i from visited.

The idea here is to explore all possible combinations of elements to form k subsets with equal sums.

If we find a valid combination, we increment count and start forming the next subset.

Let's now implement this approach in Python.

Python Code for the Less Efficient Approach

class Solution(object):
    def canPartitionKSubsets(self, nums, k):
        if sum(nums) % k != 0:
            return False

        nums.sort(reverse=True)
        target = sum(nums) / k
        visited = set()

        def backtrack(idx, count, currSum):
            if count == k:
                return True

            if target == currSum:
                return backtrack(0, count + 1, 0)

            for i in range(idx, len(nums)):
                # Skip duplicates if the last same number was skipped
                if i > 0 and (i - 1) not in visited and nums[i] == nums[i - 1]:
                    continue

                if i in visited or currSum + nums[i] > target:
                    continue

                visited.add(i)

                if backtrack(i + 1, count, currSum + nums[i]):
                    return True

                visited.remove(i)

            return False

        return backtrack(0, 0, 0)

More Efficient Approach (Backtracking)

Now, let's explore a more efficient backtracking approach that has a time complexity of 2^n.

This approach significantly reduces the time complexity compared to the previous one.

Pseudocode for the More Efficient Approach

Here's the pseudocode for the more efficient approach:

1. Calculate the target sum by dividing the sum of all elements in nums by k.
2. Sort the nums array in reverse order to prioritize larger elements.
3. Initialize a list used to keep track of whether each element in nums has been used.

4. Define a recursive function, backtrack(idx, k, subsetSum), that will explore all possible combinations:

   • idx is the current index in nums.
   • k is the number of partitions we

   still need to build.
   – subsetSum is the sum of the current subset we're building.

5. Inside the backtrack function:

   • If k is equal to 0, return True because we've successfully built all subsets.
   • If subsetSum is equal to the target, call backtrack(0, k - 1, 0) to start building the next subset.

We decrement k because we've completed one subset.
– Iterate over the elements in nums starting from index idx:
– If the element at index j is already used or adding it to subsetSum would exceed the target, continue to the next iteration.
– Mark the element at index j as used by setting used[j] to True.
– Recursively call backtrack(j + 1, k, subsetSum + nums[j]).
– Reset the usage of the element at index j by setting used[j] back to False.

The key to the efficiency of this approach is that we only make two decisions for each element: include it in the current subset or skip it.

This approach effectively explores all possible combinations with significantly fewer recursive calls compared to the previous approach.

Now, let's implement this more efficient approach in Python.

Python Code for the More Efficient Approach

class Solution(object):
    def canPartitionKSubsets(self, nums, k):
        if sum(nums) % k != 0:
            return False

        nums.sort(reverse=True)
        target = sum(nums) / k
        used = [False] * len(nums)

        def backtrack(idx, k, subsetSum):
            if k == 0:
                return True

            if subsetSum == target:
                return backtrack(0, k - 1, 0)

            for j in range(idx, len(nums)):
                if used[j] or subsetSum + nums[j] > target:
                    continue

                used[j] = True

                if backtrack(j + 1, k, subsetSum + nums[j]):
                    return True

                used[j] = False

            return False

        return backtrack(0, k, 0)

With this more efficient approach, you can solve the problem with significantly reduced time complexity.

Time and Space Complexity

Let's analyze the time and space complexity of the two approaches.

Less Efficient Approach (Backtracking)

• Time Complexity: The time complexity of this approach is O(k^n), where n is the length of the nums array.

In the worst case, we explore all possible combinations of elements.
– Space Complexity: The space complexity is O(n) due to the recursive call stack and the visited set.

More Efficient Approach (Backtracking)

• Time Complexity: The time complexity of this approach is O(2^n).

It's significantly more efficient than the previous approach because we make only two decisions (include or skip) for each element.
– Space Complexity: The space complexity is O(n) due to the recursive call stack and the used list.

Reasoning Behind Our Approach

The more efficient backtracking approach works by systematically exploring all possible combinations of elements to create k subsets with equal sums.

It minimizes the number of recursive calls and decisions made for each element.

By following this approach, we can efficiently determine whether it's possible to partition the given array into k equal sum subsets.

Related Interview Questions By Company:

• Design Linked List LeetCode
• Reorganize String LeetCode
• Lru Cache LeetCode

Related Interview Questions By Difficulty:

• Combination Sum II LeetCode
• Combination Sum LeetCode
• Maximum Length Of A Concatenated String With Unique Characters

Related Interview Questions By Category:

• Reverse String LeetCode
• Push Dominoes LeetCode
• Find Median From Data Stream LeetCode

Conclusion

In this coding session, we tackled the LeetCode problem Partition To K Equal Sum Subsets We explored two backtracking approaches to solve the problem, with a focus on the more efficient one that has a time complexity of O(2^n).

This problem provides an excellent opportunity to practice backtracking techniques and optimize solutions for efficiency.

If you have any questions, suggestions, or insights, please feel free to comment and share your thoughts.

Happy coding!

Question Link