18. Partition Equal Subset Sum

The problem can be found at the following link: Question Link

Problem Description

Given an array arr[], determine if it can be partitioned into two subsets such that the sum of elements in both parts is the same.

Each element must be in exactly one subset.

Examples

Example 1:

Input:

arr = [1, 5, 11, 5]

Output:

True

Explanation:

The array can be partitioned into [1, 5, 5] and [11], both having the sum 11.

Example 2:

Input:

arr = [1, 3, 5]

Output:

False

Explanation:

There is no way to split the array into two subsets with equal sum.

Constraints:

• $(1 \leq arr.size \leq 100)$

• $(1 \leq arr[i] \leq 200)$

Optimized 1D Dynamic Programming

Approach:

1. Calculate the total sum of the array. If it's odd, return false (cannot be evenly split).

2. Use a DP table (dp[j]), where dp[j] tells if we can form sum j.

3. Initialize dp[0] = true, since a sum of 0 is always possible.

4. Iterate through each element in the array:

   • Update dp[j] = dp[j] OR dp[j - num] for j = target down to num.

5. If dp[target] is true, we can partition the array into two subsets with equal sum.

Time and Auxiliary Space Complexity

• Expected Time Complexity: $O(N \times sum)$, as we iterate over the elements and process sums up to sum/2.

• Expected Auxiliary Space Complexity: $O(sum)$, as we use a 1D DP array of size sum/2 + 1.

Code (C++)

class Solution {
  public:
    bool equalPartition(vector<int>& arr) {
        int sum = accumulate(arr.begin(), arr.end(), 0);
        if (sum % 2) return false;
        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for (int num : arr)
            for (int j = target; j >= num; --j)
                dp[j] = dp[j] || dp[j - num];
        return dp[target];
    }
};

⚡ Alternative Approaches

2️⃣ Dynamic Programming (O(N×sum) Time, O(N×sum) Space) — 2D DP

Algorithm Steps:

1. Use a 2D DP table, where dp[i][j] represents whether a subset with sum j can be formed using the first i elements.

2. Base Case:

   • dp[0][0] = true (sum 0 can be formed with zero elements).

   • dp[i][0] = true for all i (sum 0 is always achievable).

3. Recurrence Relation: $[ dp[i][j] = dp[i-1][j] \quad \text{(exclude element)} $] If arr[i-1] ≤ j, then: $[ dp[i][j] = dp[i-1][j] \text{ OR } dp[i-1][j - arr[i-1]] $] (include element if possible).

class Solution {
  public:
    bool equalPartition(vector<int>& arr) {
        int sum = accumulate(arr.begin(), arr.end(), 0);
        if (sum % 2) return false;
        int target = sum / 2;
        int n = arr.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
        for (int i = 0; i <= n; i++) dp[i][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= arr[i-1]) dp[i][j] = dp[i][j] || dp[i-1][j - arr[i-1]];
            }
        }
        return dp[n][target];
    }
};

✅ Time Complexity: O(N × sum) ✅ Space Complexity: O(N × sum)

3️⃣ Recursive + Memoization (O(N×sum) Time, O(N×sum) Space)

Algorithm Steps:

1. Define a recursive function canPartition(i, target) that checks if a subset of arr[0...i] sums up to target.

2. Base Cases:

   • If target == 0, return true.

   • If i < 0 or target < 0, return false.

3. Recurrence Relation:

   • Exclude arr[i]: canPartition(i - 1, target).

   • Include arr[i] if arr[i] ≤ target: canPartition(i - 1, target - arr[i]).

4. Use Memoization (dp[i][target]) to avoid redundant calculations.

class Solution {
  public:
    vector<vector<int>> dp;
    bool solve(vector<int>& arr, int i, int target) {
        if (target == 0) return true;
        if (i < 0 || target < 0) return false;
        if (dp[i][target] != -1) return dp[i][target];
        return dp[i][target] = solve(arr, i - 1, target) || solve(arr, i - 1, target - arr[i]);
    }

    bool equalPartition(vector<int>& arr) {
        int sum = accumulate(arr.begin(), arr.end(), 0);
        if (sum % 2) return false;
        int target = sum / 2, n = arr.size();
        dp.assign(n, vector<int>(target + 1, -1));
        return solve(arr, n - 1, target);
    }
};

✅ Time Complexity: O(N × sum) ✅ Space Complexity: O(N × sum) (recursion stack)

Comparison of Approaches

Approach	⏱️ Time Complexity	🗂️ Space Complexity	✅ Pros	⚠️ Cons
1D DP (Space Optimized)	🟡 O(N × sum)	🟢 O(sum/2)	Best space-efficient solution	Requires careful indexing
2D DP (Tabulation)	🟡 O(N × sum)	🔴 O(N × sum)	Intuitive approach	High space usage
Recursive + Memoization	🟡 O(N × sum)	🔴 O(N × sum)	Natural recursion flow	Stack overhead

✅ Best Choice?

• If optimizing space: Use 1D DP (Space-Optimized).

• If space is not a concern: Use 2D DP (Tabulation) for easier understanding.

• For recursion lovers: Use Recursive + Memoization.

Code (Java)

class Solution {
    static boolean equalPartition(int[] arr) {
        int sum = Arrays.stream(arr).sum();
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int num : arr)
            for (int j = target; j >= num; --j)
                dp[j] |= dp[j - num];
        return dp[target];
    }
}

Code (Python)

class Solution:
    def equalPartition(self, arr):
        s = sum(arr)
        if s % 2: return False
        target, dp = s // 2, [False] * (s // 2 + 1)
        dp[0] = True
        for num in arr:
            for j in range(target, num - 1, -1):
                dp[j] |= dp[j - num]
        return dp[target]

Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count