Close Menu
    What's Hot
    Explore the coolest frontend learning platform !
    Visit NamasteDev
    Thursday, June 4

    Partition Equal Subset Sum

    Updated: Algorithms No Comments3 Mins Readdevangini123By

    Problem Statement:

    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.

    Example 1:

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

    Output: true

    Explanation: The array can be partitioned as [1, 5, 5] and [11].

    Example 2:

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

    Output: false

    Explanation: The array can be partitioned as [1, 5, 5] and [11].

    Constraints

    • 1 <= nums.length <= 200
    • 1 <= nums[i] <= 100

    Approach:

    • Do calculate the total sum of the array.
      • If the sum is odd, immediately return false because it cannot be divided into two equal subsets.
    • Do divide the total sum by 2.
      • This becomes the target sum sum we need to achieve from a subset of the array.
    • Do create a memoization table (dp).
      • dp[remS][start] will store whether it is possible to form the remaining sum remS starting from index start.
    • Do define a recursive function fn(remS, start):
      • If remS == 0, return true (subset found).
      • If remS < 0, return false (overshoot).
      • If already computed in dp, return the stored result.
    • Do iterate over all elements from start to end:
      • For each element, recursively check if choosing it (remS - arr[i]) allows reaching the target.
      • If any path returns true, store true in dp and return it.
    • Do return false if no subset works from this position.
      • Save result in dp[remS][start].
    • Do call fn(sum, 0) at the start.
      • This checks if we can form half of the total sum using elements from the beginning.

    Time & Space Complexity:

    Time Complexity: O(n*sum)

    Space Complexity: O(n*sum)

    Dry Run

    Input: arr = [1, 5, 11, 5]

    Step 0: Start canPartition([1, 5, 11, 5])
 sum = 1 + 5 + 11 + 5 = 22
 sum % 2 == 0 → target = sum / 2 = 11

 dp table: rows 0..11, cols 0..3 (all undefined)

Call fn(remS = 11, start = 0)

fn(11, 0):
 - remS != 0 and > 0
 - dp[11][0] undefined
 - Try i from 0 to 3

 i = 0 → use arr[0] = 1 → call fn(10, 1)

   fn(10, 1):
   - dp[10][1] undefined
   - Try i = 1..3

    i = 1 → use arr[1] = 5 → call fn(5, 2)

      fn(5, 2):
      - dp[5][2] undefined
      - Try i = 2..3

       i = 2 → use arr[2] = 11 → call fn(-6, 3)
         fn(-6,3): remS < 0 → return false

       i = 3 → use arr[3] = 5 → call fn(0, 4)
         fn(0,4): remS == 0 → return true

      fn(5,2): found true (from i=3)
      → dp[5][2] = true
      → return true

    fn(10,1): fn(5,2) returned true
    → dp[10][1] = true
    → return true

 fn(11,0): fn(10,1) returned true
 → dp[11][0] = true
 → return true

Result: fn(11,0) = true → canPartition returns true

Some dp entries set during recursion:
 - dp[5][2]  = true
 - dp[10][1] = true
 - dp[11][0] = true

Step End:
Return value = true  (example partition: [1,5,5] and [11])

    Output: true

    
var canPartition = function(arr) {
    let sum = arr.reduce((acc, curr) => acc + curr, 0);
    // if my total sum is odd, I can never reach 2 subset with equal sum
    if(sum % 2) return false;
    sum = sum / 2;

    let dp = Array.from({ length: sum + 1}, () => Array(arr.length).fill(undefined))

    let fn = (remS, start) => {
        if(remS == 0) return true;
        if(remS < 0) return false;

        if(dp[remS][start] != undefined) return dp[remS][start];

        for(let i=start; i < arr.length; i++){
            if(fn(remS - arr[i], i + 1)) {
                return dp[remS][start] = true;
            }
        }
        return dp[remS][start] = false;
    }

    return fn(sum, 0);
};

    
from functools import lru_cache
from typing import List

def canPartition(arr: List[int]) -> bool:
    total = sum(arr)
    if total % 2 != 0:
        return False
    target = total // 2
    n = len(arr)

    from functools import lru_cache
    @lru_cache(None)
    def dfs(rem, start):
        if rem == 0:
            return True
        if rem < 0:
            return False
        for i in range(start, n):
            if dfs(rem - arr[i], i + 1):
                return True
        return False

    return dfs(target, 0)
      
    
import java.util.Arrays;

public class Solution {
    private Integer[][] dp;
    private int[] arr;

    public boolean canPartition(int[] nums) {
        arr = nums;
        int total = 0;
        for (int x : arr) total += x;
        if (total % 2 != 0) return false;
        int target = total / 2;
        dp = new Integer[target + 1][arr.length];
        return dfs(target, 0);
    }

    private boolean dfs(int rem, int start) {
        if (rem == 0) return true;
        if (rem < 0) return false;
        if (dp[rem][start] != null) return dp[rem][start];
        for (int i = start; i < arr.length; i++) {
            if (dfs(rem - arr[i], i + 1)) {
                dp[rem][start] = 1;
                return true;
            }
        }
        dp[rem][start] = 0;
        return false;
    }
}

    
#include <bits/stdc++.h>     
using namespace std;

bool dfs(int rem, int start, const vector& arr, vector>& dp) {
    if (rem == 0) return true;
    if (rem < 0) return false;
    if (dp[rem][start] != -1) return dp[rem][start];

    int n = arr.size();
    for (int i = start; i < n; ++i) {
        if (dfs(rem - arr[i], i + 1, arr, dp)) {
            dp[rem][start] = 1;
            return true;
        }
    }
    dp[rem][start] = 0;
    return false;
}

bool canPartition(vector arr) {
    int total = accumulate(arr.begin(), arr.end(), 0);
    if (total % 2 != 0) return false;
    int target = total / 2;
    int n = arr.size();
    vector> dp(target + 1, vector(n, -1));
    return dfs(target, 0, arr, dp);
}

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

int n;
int *arr;
int **dp; // dp[rem][start], -1 unknown, 0 false, 1 true
int dfs(int rem, int start) {
    if (rem == 0) return 1;
    if (rem < 0) return 0;
    if (dp[rem][start] != -1) return dp[rem][start];
    for (int i = start; i < n; ++i) {
        if (dfs(rem - arr[i], i + 1)) {
            dp[rem][start] = 1;
            return 1;
        }
    }
    dp[rem][start] = 0;
    return 0;
}
int canPartition(int *input, int length) {
    arr = input;
    n = length;
    int total = 0;
    for (int i = 0; i < n; ++i) total += arr[i];
    if (total % 2 != 0) return 0;
    int target = total / 2;

    // allocate dp: (target+1) x n
    dp = (int**) malloc((target + 1) * sizeof(int*));
    for (int i = 0; i <= target; ++i) {
        dp[i] = (int*) malloc(n * sizeof(int));
        for (int j = 0; j < n; ++j) dp[i][j] = -1;
    }
    int res = dfs(target, 0);
    for (int i = 0; i <= target; ++i) free(dp[i]);
    free(dp);
    return res;
}
 
    
using System;
using System.Linq;

class Solution {
    static int[][] dp;
    static int[] arr;
    static bool Dfs(int rem, int start) {
        if (rem == 0) return true;
        if (rem < 0) return false;
        if (dp[rem][start] != int.MinValue) return dp[rem][start] == 1;

        for (int i = start; i < arr.Length; i++) {
            if (Dfs(rem - arr[i], i + 1)) {
                dp[rem][start] = 1;
                return true;
            }
        }
        dp[rem][start] = 0;
        return false;
    }
    public static bool CanPartition(int[] input) {
        arr = input;
        int total = arr.Sum();
        if (total % 2 != 0) return false;
        int target = total / 2;
        dp = new int[target + 1][];
        for (int i = 0; i <= target; i++) {
            dp[i] = Enumerable.Repeat(int.MinValue, arr.Length).ToArray();
        }
        return Dfs(target, 0);
    }
}
    `

    Keep Reading

    Add A Comment
    Leave A Reply

    Demo

    Courses

    Community

    Contact Us