416. Partition Equal Subset Sum LeetCode Solution

In this guide, you will get 416. Partition Equal Subset Sum LeetCode Solution with the best time and space complexity. The solution to Partition Equal Subset Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Partition Equal Subset Sum solution in C++
Partition Equal Subset Sum solution in Java
Partition Equal Subset Sum solution in Python
Additional Resources

416. Partition Equal Subset Sum LeetCode Solution image

Problem Statement of Partition Equal Subset Sum

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 cannot be partitioned into equal sum subsets.

Constraints:

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

Complexity Analysis

Time Complexity: O(nk), where k = \Sigma |\texttt{nums[i]}| / 2
Space Complexity: O(nk)

416. Partition Equal Subset Sum LeetCode Solution in C++

class Solution {
 public:
  bool canPartition(vector<int>& nums) {
    const int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2 == 1)
      return false;
    return knapsack(nums, sum / 2);
  }

 private:
  bool knapsack(const vector<int>& nums, int subsetSum) {
    const int n = nums.size();
    // dp[i][j] := true if j can be formed by nums[0..i)
    vector<vector<bool>> dp(n + 1, vector<bool>(subsetSum + 1));
    dp[0][0] = true;

    for (int i = 1; i <= n; ++i) {
      const int num = nums[i - 1];
      for (int j = 0; j <= subsetSum; ++j)
        if (j < num)
          dp[i][j] = dp[i - 1][j];
        else
          dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
    }

    return dp[n][subsetSum];
  }
};
/* code provided by PROGIEZ */

416. Partition Equal Subset Sum LeetCode Solution in Java

class Solution {
  public boolean canPartition(int[] nums) {
    final int sum = Arrays.stream(nums).sum();
    if (sum % 2 == 1)
      return false;
    return knapsack(nums, sum / 2);
  }

  private boolean knapsack(int[] nums, int subsetSum) {
    final int n = nums.length;
    // dp[i][j] := true if j can be formed by nums[0..i)
    boolean[][] dp = new boolean[n + 1][subsetSum + 1];
    dp[0][0] = true;

    for (int i = 1; i <= n; ++i) {
      final int num = nums[i - 1];
      for (int j = 0; j <= subsetSum; ++j)
        if (j < num)
          dp[i][j] = dp[i - 1][j];
        else
          dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];
    }

    return dp[n][subsetSum];
  }
}
// code provided by PROGIEZ

416. Partition Equal Subset Sum LeetCode Solution in Python

class Solution:
  def canPartition(self, nums: list[int]) -> bool:
    summ = sum(nums)
    if summ % 2 == 1:
      return False
    return self.knapsack_(nums, summ // 2)

  def knapsack_(self, nums: list[int], subsetSum: int) -> bool:
    n = len(nums)
    # dp[i][j] := True if j can be formed by nums[0..i)
    dp = [[False] * (subsetSum + 1) for _ in range(n + 1)]
    dp[0][0] = True

    for i in range(1, n + 1):
      num = nums[i - 1]
      for j in range(subsetSum + 1):
        if j < num:
          dp[i][j] = dp[i - 1][j]
        else:
          dp[i][j] = dp[i - 1][j] or dp[i - 1][j - num]

    return dp[n][subsetSum]
 # code by PROGIEZ