416. Partition Equal Subset Sum

Time: O(n x sum)

Space: O(sum)

Intuition

Can we find a subset summing to exactly half the total? This is a classic 0/1 knapsack: can we fill a knapsack of capacity sum/2 using each number at most once?

Algorithm

1Compute total. If odd, return false.
2Target = total / 2. Create boolean DP array dp[0..target], dp[0]=true.
3For each number n, iterate j from target down to n: dp[j] |= dp[j-n].
4Return dp[target].

Example Walkthrough

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

1.total=22, target=11.
2.After 1: dp[1]=true.
3.After 5: dp[5]=dp[6]=true.
4.After 11: dp[11]=true.

Output: true

Common Pitfalls

•Iterate j backwards to avoid using same element twice.
•If total is odd, immediately return false.

416.cs

// Approach: 0/1 Knapsack DP — check whether any subset sums to totalSum / 2.
// If totalSum is odd, partitioning is impossible.
// Create a boolean dp array of size (target + 1): dp[t] = true if some subset sums to t.
// Process each number: iterate t from target down to num and set dp[t] |= dp[t - num].
// Iterating backwards prevents using the same element twice (0/1 knapsack rule).
// If dp[target] is true at the end, an equal-sum partition exists.
// Time: O(n x sum) Space: O(sum) using a 1D bit array.

public class Solution
{
    public bool CanPartition(int[] nums)
    {
        int n = nums.Length;
        int totalSum = 0;

        for (int i = 0; i < nums.Length; i++)
            totalSum += nums[i];

        if (totalSum % 2 > 0)
            return false;
        else
            return tabulation(n, totalSum / 2, nums);
    }

    private bool tabulation(int n, int k, int[] arr)
    {
        bool[][] dp = new bool[n + 1][];

        for (int i = 0; i <= n; i++)
            dp[i] = new bool[k + 1];

        for (int i = 0; i <= n; i++)
            dp[i][0] = true;

        for (int i = 1; i <= k; i++)
            dp[0][i] = false;

        for (int ind = 1; ind <= n; ind++)
        {
            for (int target = 1; target <= k; target++)
            {
                if (target >= arr[ind - 1])
                    dp[ind][target] = dp[ind - 1][target] || dp[ind - 1][target - arr[ind - 1]];
                else
                    dp[ind][target] = dp[ind - 1][target];
            }
        }

        return dp[n][k];
    }
}

Was this solution helpful?