ByteInTheSky

Partition Equal Subset Sum

Tagged: Array, Dynamic Programming

Problem

We are given a non-empty array of positive integers nums. Our task is to check whether this array can be divided into two subsets such that the sum of both subsets are equal.

For example,

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

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

Solution

Brute Force

public bool CanPartition(int[] nums)
{
    int sum = nums.Sum();
    if (sum % 2 == 1)
        return false;

    int subSetSum = sum / 2;
    return CanPartition(nums.Length - 1, subSetSum);

    bool CanPartition(int n, int subSetSum)
    {
        if (subSetSum == 0)
            return true;
        if (n == 0 || subSetSum < 0)
            return false;
        return CanPartition(n - 1, subSetSum - nums[n - 1]) || CanPartition(n - 1, subSetSum);
    }
}

Complexity Analysis

  • Time Complexity: At each step we generate two subtree and the height of the tree is n. The total number of generated nodes is 2n. Since, we traverse all the nodes, then the complexity will be O(2n).
  • Space Complexity: The complexity will be the same with O(recursion depth), thus it will be O(n).

Top-down Dynamic Programming

public bool CanPartition(int[] nums)
{
    int sum = nums.Sum();
    if (sum % 2 == 1)
        return false;

    int subSetSum = sum / 2;
    Dictionary<(int, int), bool> memo = new Dictionary<(int, int), bool>();
    return CanPartition(nums.Length - 1, subSetSum);

    bool CanPartition(int n, int subSetSum)
    {
        if (subSetSum == 0)
            return true;
        if (n == 0 || subSetSum < 0)
            return false;

        if (memo.TryGetValue((n, subSetSum), out var value))
            return value;

        bool result = CanPartition(n - 1, subSetSum - nums[n - 1]) || CanPartition(n - 1, subSetSum);
        memo.Add((n, subSetSum), result);

        return result;
    }
}

Complexity Analysis

Suppose N is the length of nums and M equals the subSetSum.

  • Time Complexity: This problem doesn’t guarantee to have overlapping subproblem unlike typical dynamic programming problem. Therefore, in the worst case the time complexity is O(N x M).
  • Space Complexity: The memo will contain N x M entries and the recursion stack will allocate spaces as many as the depth of recursive call (tree), thus the complexity will be O(N x M) since N x M is the dominant part.

Bottom-up Dynamic Programming

public bool CanPartition(int[] nums)
{
    int sum = nums.Sum();
    if (sum % 2 == 1)
        return false;

    int subSetSum = sum / 2;
    int n = nums.Length;
    bool[,] dp = new bool[n + 1, subSetSum + 1];
    dp[0, 0] = true;
    for (int i = 1; i <= n; i++)
    {
        int curr = nums[i - 1];
        for (int j = 0; j <= subSetSum; j++)
        {
            if (j < curr)
                dp[i, j] = dp[i - 1, j];
            else
                dp[i, j] = dp[i - 1, j] || (dp[i - 1, j - curr]);
        }
    }
    return dp[n, subSetSum];
}

Complexity Analysis

Suppose N is the length of nums and M equals the subSetSum.

  • Time Complexity: Since we have nested loop where the outer loop has length N and the inner loop has length M, then the time complexity is O(N x M).
  • Space Complexity: Since the dp array will allocate around N x M spaces, then the complexity will be O(N x M).
← C# Delegate Equivalent in Java
Paint Fence →