Partition Equal Subset Sum - Practice Coding Problems

Partition Equal Subset Sum - Problem

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal, or false otherwise.

Key Points:

Each element can only be used once
Both subsets must contain at least one element
The order of elements within subsets doesn't matter

Input & Output

Example 1 — Basic Partition

$ Input: nums = [1,5,11,5]

› Output: true

💡 Note: Array can be partitioned as [1,5,5] and [11]. Both subsets have sum = 11.

Example 2 — Cannot Partition

$ Input: nums = [1,2,3,5]

› Output: false

💡 Note: Total sum = 11 (odd), so cannot be split into two equal subsets.

Example 3 — Minimum Case

$ Input: nums = [1,1]

› Output: true

💡 Note: Can partition as [1] and [1]. Both subsets have sum = 1.

Constraints

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Array of integers to partition

Process

Find if we can split into two equal-sum subsets

Output

Return true if partition possible, false otherwise

Key Takeaway

🎯 Key Insight: We only need to check if one subset with sum = total/2 exists

Asked in

a Amazon 45 G Google 38 f Facebook 32 M Microsoft 28

The key insight is that we only need to find if one subset with sum = total/2 exists, as the remaining elements automatically form the other subset. The optimal 1D DP approach tracks achievable sums efficiently. Time: O(n × sum), Space: O(sum).

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking with Pruning	O(2^n)	O(n)	Use recursion to explore all possibilities but prune branches early when sum exceeds target
1D Dynamic Programming	O(n × sum)	O(sum)	Use a boolean array to track all achievable sums using subset of elements
Brute Force - Try All Subsets	O(2^n)	O(1)	Generate all possible subsets and check if any has sum equal to half the total
Memoization (Top-Down DP)	O(n × sum)	O(n × sum)	Use recursion with memoization to avoid recomputing the same subproblems

Backtracking with Pruning — Algorithm Steps

Check if total sum is even
Use recursive function to try including/excluding each element
Prune branches when current sum exceeds target

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int backtrack(int* nums, int numsSize, int index, int currentSum, int target) {
    if (currentSum == target) {
        return 1;
    }
    if (index >= numsSize || currentSum > target) {
        return 0;
    }
    
    // Include current element or exclude it
    return backtrack(nums, numsSize, index + 1, currentSum + nums[index], target) ||
           backtrack(nums, numsSize, index + 1, currentSum, target);
}

int solution(int* nums, int numsSize) {
    int total = 0;
    for (int i = 0; i < numsSize; i++) {
        total += nums[i];
    }
    
    if (total % 2 != 0) {
        return 0;
    }
    
    int target = total / 2;
    return backtrack(nums, numsSize, 0, 0, target);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[200];
    int numsSize = 0;
    
    char* ptr = line + 1; // Skip '['
    char* token = strtok(ptr, ",]");
    
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, numsSize);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

In worst case, explore all subset combinations with pruning

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion call stack depth up to n levels

⚡ Linearithmic Space

185.0K Views

High Frequency

~25 min Avg. Time

8.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen