How to Solve: Partition Equal Subset Sum

How to Solve: Partition Equal Subset Sum

(A Complete FAANG-Level Interview Guide)

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you prove you can break down NP-hard problems into efficient dynamic programming solutions under pressure."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Dynamic Programming (DP) Basics – Memoization, tabulation, and state transitions. 2. Subset Sum Problem – The classic DP problem where you check if a subset sums to a target. 3. Bitmasking (Optional) – Useful for space optimization in some variants.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Run this checklist for every "Partition Equal Subset Sum" problem.)

1. Check Total Sum Parity
2. If the total sum is odd → immediately return False (no possible partition).

3. If even → proceed.

4. Define Target

5. target = total_sum // 2 (since we need two subsets of equal sum).

6. Choose DP Approach

7. Option 1 (2D DP): dp[i][j] = True if subset of first i elements sums to j.

8. Option 2 (1D DP): Optimize space by reusing a single array.

9. Initialize DP Table

10. dp[0] = True (empty subset sums to 0).

11. All other entries start as False.

12. Fill DP Table

13. For each number, update the DP array in reverse to avoid overwriting.

14. for j in range(target, nums[i]-1, -1): dp[j] = dp[j] or dp[j-nums[i]]

15. Return Result

16. return dp[target]

? WORKED EXAMPLES

Example 1 – Basic (LeetCode 416)

Problem: Given an array nums, return True if it can be partitioned into two subsets with equal sum.

Solution (1D DP):

def canPartition(nums):

    total = sum(nums)

    if total % 2 != 0: return False

    target = total // 2

    dp = [False]  (target + 1)

    dp[0] = True  # Base case: empty subset


    for num in nums:

        for j in range(target, num - 1, -1):

            dp[j] = dp[j] or dp[j - num]

    return dp[target]

Time Complexity: O(n target) (pseudo-polynomial) Space Complexity: O(target) Why this works: We check all possible subset sums up to target using DP, ensuring we don’t recompute overlapping subproblems.

Example 2 – Medium (With Duplicates)

Problem: Same as above, but nums may contain duplicates. Does this change the solution?

Solution: - No change! The DP approach naturally handles duplicates because it processes each number independently. - Edge Case: If all numbers are the same (e.g., [1,1,1,1]), the solution still works.

Time/Space Complexity: Same as above.

Example 3 – Hard (Follow-Up: Minimum Subset Sum Difference)

Problem: Given nums, partition into two subsets such that the difference between their sums is minimized.

Solution (Modified DP):

def minSubsetSumDifference(nums):

    total = sum(nums)

    target = total // 2

    dp = [False]  (target + 1)

    dp[0] = True


    for num in nums:

        for j in range(target, num - 1, -1):

            dp[j] = dp[j] or dp[j - num]


    # Find the largest j <= target where dp[j] is True

    for j in range(target, -1, -1):

        if dp[j]:

            return total - 2  j

    return total

Time Complexity: O(n target) Space Complexity: O(target) Why this works: We reuse the DP approach but now find the closest possible sum to total/2 to minimize the difference.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. First, check if the total sum is even—if not, return False immediately. If it is, your target is half the sum. Use a 1D DP array where dp[j] tracks if a subset sums to j. Initialize dp[0] = True, then iterate backward through the array to avoid overwriting. For each number, update the DP array from the target down to the number’s value. Finally, return dp[target]. This approach runs in O(n target) time and O(target) space. If the interviewer throws in negatives or asks for optimizations, pivot to bitmasking or backtracking. You’ve got this—now go crush that interview!

? Final Notes

• Practice Variations: Try "Partition into K equal subsets" (LeetCode 698) for a harder challenge.
• Whiteboard Tip: Always write the DP state transition (dp[j] = dp[j] or dp[j-num]) clearly.
• Time Management: If stuck, start with brute-force (backtracking) and optimize to DP.

This guide is 100% interview-ready—use it to dominate your next FAANG coding round! ?