[Dynamic Programming] Partition Equal Subset Sum - Medium

The Partition Equal Subset Sum problem is a well-known challenge in dynamic programming. It asks if we can split a set into two groups that have the same total sum. To solve this, we need to check if we can find a group in the set that adds up to half of the total sum of all elements. We can solve this problem well using dynamic programming. This way, we can explore possible groups without repeating our work.

In this article, we will look closely at the Partition Equal Subset Sum problem. We will explain its definition and what the problem is about. We will talk about different dynamic programming methods in Java, Python, and C++. We will also discuss how to make our space use better. Plus, we will look at recursive methods with memoization and ways to solve it step by step. We will also give a full analysis of the time it takes to run our solutions. By the end of this article, we will understand how to solve the Partition Equal Subset Sum problem.

  • Dynamically Solving Partition Equal Subset Sum Problem - Medium
  • Understanding the Problem Statement for Partition Equal Subset Sum
  • Dynamic Programming Approach for Partition Equal Subset Sum in Java
  • Dynamic Programming Approach for Partition Equal Subset Sum in Python
  • Dynamic Programming Approach for Partition Equal Subset Sum in C++
  • Optimizing Space Complexity for Partition Equal Subset Sum
  • Recursive Approach with Memoization for Partition Equal Subset Sum
  • Iterative Approach for Partition Equal Subset Sum
  • Time Complexity Analysis for Partition Equal Subset Sum
  • Frequently Asked Questions

If we want to learn more about dynamic programming techniques, we can check out related articles. They can help us understand better. Some of them are Dynamic Programming on Fibonacci Numbers and Dynamic Programming with Memoization.

Understanding the Problem Statement for Partition Equal Subset Sum

The Partition Equal Subset Sum problem is a well-known issue in computer science. It asks if we can split a set of non-negative numbers into two groups. The sum of the numbers in both groups should be the same.

Problem Statement

We have an array of integers called nums. Our job is to check if we can split it into two groups with equal sums. We need to follow these rules:

  1. The total sum of all numbers in the array must be even. If the total sum is odd, we cannot split it into two equal groups.
  2. If the total sum is even, we call it totalSum. We need to find one group that adds up to totalSum / 2.
  3. We can use dynamic programming methods to solve the problem.

Example

Let us look at the input array:

nums = [1, 5, 11, 5]
  • The total sum is 1 + 5 + 11 + 5 = 22, which is even.
  • We need to find a group that adds up to 22 / 2 = 11.
  • One way to split it is [1, 5, 5] and [11]. Both groups add up to 11.

Constraints

  • The length of nums can be from 1 to 200.
  • Each number can be from 0 to 1000.

Our aim is to create a smart algorithm that can find out if we can make such a split. We will use dynamic programming to make the solution better.

Dynamic Programming Approach for Partition Equal Subset Sum in Java

To solve the Partition Equal Subset Sum problem using dynamic programming in Java, we need to check if we can split a set into two groups. These groups must have the same total. If the total sum of the array is odd, we cannot split it. So first, we check if the total sum is even. If it is even, we then look for a group that adds up to half of the total sum.

Steps to Implement:

  1. Find the total sum of the array.
  2. If the total sum is odd, we return false.
  3. Create a boolean DP array. In this array, dp[j] tells if we can make a group with sum j.
  4. Go through the numbers in the array and update the DP array.

Java Code Implementation:

public class PartitionEqualSubsetSum {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        // If total sum is odd, we cannot partition it into two equal subsets
        if (totalSum % 2 != 0) {
            return false;
        }
        
        int target = totalSum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true; // A sum of 0 can always be achieved
        
        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        
        return dp[target];
    }

    public static void main(String[] args) {
        PartitionEqualSubsetSum solution = new PartitionEqualSubsetSum();
        int[] nums = {1, 5, 11, 5};
        System.out.println(solution.canPartition(nums)); // Output: true
    }
}

Explanation:

  • The canPartition method finds the total sum of the input array.
  • It checks if the total sum is even. If it is not even, it returns false.
  • The dp array starts to track sums we can make up to the target sum.
  • The loops update the dp array based on the numbers in the input array.
  • In the end, it checks if we can make the target sum.

This way we use dynamic programming to solve the Partition Equal Subset Sum problem. The time complexity is O(n * target) and the space complexity is O(target).

Dynamic Programming Approach for Partition Equal Subset Sum in Python

We can solve the Partition Equal Subset Sum problem well using a dynamic programming method. Our goal is to check if we can split a set into two subsets. Both subsets should have the same sum.

Problem Formulation

We start with a set of numbers. First, we need to find the total sum. If the total sum is odd, we cannot split the set into two equal parts. In this case, we return False. If the sum is even, we look for a subset that has a sum equal to half of the total sum. We call this half target.

Dynamic Programming Solution

We will make a boolean array called dp. In this array, dp[i] is True if we can form a subset with sum i from the numbers we have.

Python Code Implementation

def canPartition(nums):
    total_sum = sum(nums)
    
    # If the total sum is odd, we cannot split it into two equal subsets
    if total_sum % 2 != 0:
        return False
    
    target = total_sum // 2
    dp = [False] * (target + 1)
    dp[0] = True  # A sum of 0 can always be formed with no elements
    
    for num in nums:
        # Traverse backwards to ensure we do not use the same number more than once
        for i in range(target, num - 1, -1):
            dp[i] = dp[i] or dp[i - num]
    
    return dp[target]

# Example usage:
nums = [1, 5, 11, 5]
print(canPartition(nums))  # Output: True

Explanation of the Code

  1. Calculate Total Sum: We find the total sum of the input list.
  2. Check for Odd Total: If the total sum is odd, we return False.
  3. Initialize DP Array: We create a DP array that is size target + 1. We set dp[0] to True because we can always get a sum of 0.
  4. Filling the DP array: For each number in the list, we update the DP array from back to front. This way, we do not count the same number more than once.
  5. Return Result: Finally, we return dp[target]. This tells us if a subset with the target sum exists.

This method runs in O(n * target) time. Here, n is the number of elements in the list. The space we use is O(target) because of the DP array.

For more about dynamic programming, we can look at the Dynamic Programming: Coin Change Problem. It is a similar use of dynamic programming techniques.

Dynamic Programming Approach for Partition Equal Subset Sum in C++

The Partition Equal Subset Sum problem is about checking if we can split a set into two groups. The sum of the numbers in both groups should be the same. We can use the dynamic programming method to solve this. It is based on the subset sum problem.

Problem Breakdown

  1. Input: An array nums of non-negative numbers.
  2. Goal: We want to see if there is a group of nums that adds up to total/2. Here, total is the sum of all numbers in nums.
  3. Condition: If total is odd, we cannot split the set.

Dynamic Programming Table

We use a 2D boolean array dp. The value dp[i][j] shows if we can make a sum j using the first i numbers from the array.

C++ Implementation

#include <iostream>
#include <vector>

bool canPartition(std::vector<int>& nums) {
    int total = 0;
    for (int num : nums) {
        total += num;
    }
    if (total % 2 != 0) return false;

    int target = total / 2;
    int n = nums.size();
    std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(target + 1, false));

    // Initialize the dp array
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = true; // Sum 0 is always possible
    }

    // Fill the dp table
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= target; ++j) {
            if (j < nums[i - 1]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }

    return dp[n][target];
}

int main() {
    std::vector<int> nums = {1, 5, 11, 5};
    if (canPartition(nums)) {
        std::cout << "Can partition the array into two subsets of equal sum." << std::endl;
    } else {
        std::cout << "Cannot partition the array into two subsets of equal sum." << std::endl;
    }
    return 0;
}

Explanation of the Code

  • We first find the total sum of the input array.
  • If the total is odd, we return false right away.
  • Then, we set up a DP table to track possible sums.
  • The loops fill this table. We decide to include or exclude each number.
  • At the end, we check if dp[n][target] is true. This means we can split the set.

This C++ solution uses dynamic programming well. It checks if we can split the array into two equal sum groups. The time needed is O(n * target) and the space used is O(n * target). For more on similar problems, look at Dynamic Programming - Coin Change.

Optimizing Space Complexity for Partition Equal Subset Sum

We can make the space use better for the Partition Equal Subset Sum problem by using a 1D array instead of a 2D array. This problem asks if we can split a set into two subsets with the same sum. We need to look at the sums we can get instead of the actual subsets.

Approach

  1. Define the Target Sum: We get the target sum by taking half of the total sum of the array. If the total sum is odd, we cannot split it into two equal subsets.

  2. Initialize a 1D Array: We create a boolean array dp with size target + 1. The dp[j] tells us if we can make a subset with sum j.

  3. Iterate Through the Array: For each number in the input array, we update the dp array from the back to avoid changing results we still need.

Code Implementation

Java

public boolean canPartition(int[] nums) {
    int total = 0;
    for (int num : nums) total += num;
    if (total % 2 != 0) return false;
    
    int target = total / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;

    for (int num : nums) {
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    
    return dp[target];
}

Python

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    
    return dp[target]

C++

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        if (total % 2 != 0) return false;

        int target = total / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;

        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        
        return dp[target];
    }
};

Space Complexity

  • The space complexity is O(target) now instead of O(n * target). Here, n is how many elements are in the input array. This change helps us deal with bigger inputs better.

By using this better way, we improve how the Partition Equal Subset Sum problem works while keeping the code clear and useful. For more about dynamic programming, we can look at topics like Dynamic Programming - Coin Change.

Recursive Approach with Memoization for Partition Equal Subset Sum

We can solve the Partition Equal Subset Sum problem using a recursive way with memoization. This method helps by saving results from our calculations. So we do not need to do the same work again.

Problem Definition

We have a set of integers. Our goal is to see if we can split it into two groups. The sum of numbers in both groups should be the same. The recursive function will check if we can create a group with a specific sum using the numbers in the array.

Recursive Function with Memoization

The recursive function needs three things: the current position in the array, the sum we still need, and a memoization table to keep the results we have already found.

Java Implementation

import java.util.Arrays;

public class PartitionEqualSubsetSum {
    public boolean canPartition(int[] nums) {
        int totalSum = Arrays.stream(nums).sum();
        if (totalSum % 2 != 0) return false; // If total sum is odd we cannot split

        int target = totalSum / 2;
        Boolean[][] memo = new Boolean[nums.length][target + 1];
        return canPartitionRecursive(nums, nums.length - 1, target, memo);
    }

    private boolean canPartitionRecursive(int[] nums, int index, int sum, Boolean[][] memo) {
        if (sum == 0) return true; // We found a group with the right sum
        if (index < 0 || sum < 0) return false; // Out of bounds or negative sum

        if (memo[index][sum] != null) return memo[index][sum]; // Return saved result

        // We can include the current number or not
        boolean include = canPartitionRecursive(nums, index - 1, sum - nums[index], memo);
        boolean exclude = canPartitionRecursive(nums, index - 1, sum, memo);

        memo[index][sum] = include || exclude; // Save the result
        return memo[index][sum];
    }
}

Python Implementation

def can_partition(nums):
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False  # If total sum is odd we cannot split

    target = total_sum // 2
    memo = {}
    return can_partition_recursive(nums, len(nums) - 1, target, memo)

def can_partition_recursive(nums, index, sum_remaining, memo):
    if sum_remaining == 0:
        return True  # We found a group with the right sum
    if index < 0 or sum_remaining < 0:
        return False  # Out of bounds or negative sum

    if (index, sum_remaining) in memo:
        return memo[(index, sum_remaining)]  # Return saved result

    # We can include the current number or not
    include = can_partition_recursive(nums, index - 1, sum_remaining - nums[index], memo)
    exclude = can_partition_recursive(nums, index - 1, sum_remaining, memo)

    memo[(index, sum_remaining)] = include or exclude  # Save the result
    return memo[(index, sum_remaining)]

C++ Implementation

#include <vector>
#include <numeric>

class Solution {
public:
    bool canPartition(std::vector<int>& nums) {
        int totalSum = std::accumulate(nums.begin(), nums.end(), 0);
        if (totalSum % 2 != 0) return false;  // If total sum is odd we cannot split

        int target = totalSum / 2;
        std::vector<std::vector<int>> memo(nums.size(), std::vector<int>(target + 1, -1));
        return canPartitionRecursive(nums, nums.size() - 1, target, memo);
    }

private:
    bool canPartitionRecursive(std::vector<int>& nums, int index, int sum, std::vector<std::vector<int>>& memo) {
        if (sum == 0) return true;  // We found a group with the right sum
        if (index < 0 || sum < 0) return false;  // Out of bounds or negative sum

        if (memo[index][sum] != -1) return memo[index][sum];  // Return saved result

        // We can include the current number or not
        bool include = canPartitionRecursive(nums, index - 1, sum - nums[index], memo);
        bool exclude = canPartitionRecursive(nums, index - 1, sum, memo);

        memo[index][sum] = include || exclude;  // Save the result
        return memo[index][sum];
    }
};

Key Points

The recursive way with memoization makes the time to solve this problem much shorter than a simple recursive way. This method uses the idea of repeating problems and keeps results in a memoization table. It works well for medium input sizes where the total sum is not too big.

Iterative Approach for Partition Equal Subset Sum

We use the iterative approach to solve the Partition Equal Subset Sum problem. This method uses a dynamic programming table. It helps us build solutions based on values we already calculated. Our goal is to find out if we can split a given set into two subsets. The sum of the elements in both subsets should be the same.

Problem Statement

We have an array called nums. We need to check if it can be divided into two subsets with equal sum. The target sum for each subset is totalSum/2. Here, totalSum is the total of all elements in nums. If totalSum is odd, we can quickly say false.

Steps to Implement the Iterative Approach

  1. First, we calculate the total sum of the array. If it is odd, we return false.
  2. Next, we set up a boolean DP array dp that is target + 1 in size. The target is totalSum / 2.
  3. We set dp[0] = true because we can always make a sum of 0 with an empty subset.
  4. We go through each number in nums and update the DP table from the back. This way, we do not overwrite any values.
  5. The final answer will be in dp[target].

Java Implementation

public boolean canPartition(int[] nums) {
    int totalSum = 0;
    for (int num : nums) totalSum += num;

    if (totalSum % 2 != 0) return false;
    int target = totalSum / 2;
    
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;

    for (int num : nums) {
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }

    return dp[target];
}

Python Implementation

def canPartition(nums):
    total_sum = sum(nums)
    
    if total_sum % 2 != 0:
        return False
    
    target = total_sum // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]

    return dp[target]

C++ Implementation

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        
        if (totalSum % 2 != 0) return false;
        int target = totalSum / 2;
        
        vector<bool> dp(target + 1, false);
        dp[0] = true;

        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }

        return dp[target];
    }
};

Time Complexity

The time complexity for the iterative approach is O(n * target). Here, n is the number of elements in nums and target is totalSum / 2. The space complexity is O(target) because of the DP array we use.

This iterative dynamic programming method checks if we can divide the given array into two subsets with equal sum. It is a basic technique for solving similar subset-sum problems. For more reading on related topics, you can check articles on Dynamic Programming - Coin Change and Dynamic Programming - Unique Paths.

Time Complexity Analysis for Partition Equal Subset Sum

We can solve the Partition Equal Subset Sum problem using dynamic programming. The time it takes to solve this problem mainly depends on how many items we have and the target sum from the input array.

  1. Dynamic Programming Table Construction:
    • Let ( n ) be the number of items in the array. Let ( S ) be the total sum of the items.
    • We need to find if there is a subset that adds up to ( S/2 ).
    • The dynamic programming method uses a 2D table dp[n+1][S/2 + 1]. Here:
      • The rows show the items (from 0 to ( n )).
      • The columns show the possible sums (from 0 to ( S/2 )).
    • This gives us a time complexity of ( O(n S) ).
  2. Space Optimization:
    • We can make the space needed smaller. Instead of using a 2D array, we can use a 1D array. This gives us a space complexity of ( O(S) ):
      • We only need the current and previous states to find the answer.
    • The time complexity is still ( O(n S ). But now, the space needed is less.
  3. Example:
    • Let’s take the array ([1, 5, 11, 5]) which has a total sum ( S = 22 ).
    • We will look for a subset sum of ( 11 ).
    • The DP table will be ( 5 ) (for 4 items and sums from 0 to 11).
  4. Final Time Complexity:
    • So, the total time complexity to solve the Partition Equal Subset Sum problem using dynamic programming is:
      • ( O(n S) ). Here ( n ) is the number of items and ( S ) is the target sum ( S/2 ).

This analysis shows how we can use dynamic programming to solve the Partition Equal Subset Sum problem efficiently in terms of time and space.

For more information about dynamic programming, we can check articles like Dynamic Programming - Coin Change and Dynamic Programming - Longest Increasing Subsequence.

Frequently Asked Questions

What is the Partition Equal Subset Sum problem?

The Partition Equal Subset Sum problem is a well-known challenge in algorithms. It asks if we can split a set of numbers into two groups with the same total. This problem uses dynamic programming. We create a solution by solving smaller problems step by step. Knowing this problem helps us learn dynamic programming better.

How can I implement the dynamic programming approach for the Partition Equal Subset Sum in Java?

To use dynamic programming for the Partition Equal Subset Sum problem in Java, we can make a 2D boolean array. This array shows if we can reach certain sums with subsets. The outer loop goes through the numbers. The inner loop checks for possible sums. For a full example, check our Dynamic Programming Approach for Partition Equal Subset Sum in Java.

What is the time complexity of the Partition Equal Subset Sum algorithm?

The time complexity for the dynamic programming approach for the Partition Equal Subset Sum problem is O(n * sum). Here ‘n’ is the count of numbers in the array. ‘sum’ is half of the total sum of the numbers. This complexity comes from the nested loops we use to fill the DP table. Looking at time complexity helps us make solutions better for large inputs.

Can the Partition Equal Subset Sum problem be solved using recursion?

Yes, we can solve the Partition Equal Subset Sum problem with recursion. We often add memoization to avoid doing the same work again. This method checks all possible groups to see if we can find a valid split. For more details, see our section on the Recursive Approach with Memoization for Partition Equal Subset Sum.

How does space complexity affect the Partition Equal Subset Sum solution?

Space complexity is very important in dynamic programming for the Partition Equal Subset Sum problem. The usual DP method uses O(n * sum) space because of the 2D array. But we can make it better to O(sum) by using a 1D array and updating it directly. This change is important for saving memory. For more info, check our section on Optimizing Space Complexity for Partition Equal Subset Sum.