Jobs

Interviews

Discussions

Partition Equal Subset Sum

Medium

Asked by:

+13

57 views

Topics:

Dynamic Programming

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

Partition Equal Subset Sum

Medium

Asked by:

57 views

Topics:

Dynamic Programming

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array, `nums`?
Can the input array `nums` contain negative integers or zero values?
Are there any constraints on the range of values within the integer array `nums`?
If a partition is not possible, should I return `false`?
Are duplicate numbers allowed in the input array, and if so, how should they be handled?

Brute Force Solution

Approach

We're trying to see if a collection of numbers can be split into two groups that have the same total. The brute force way is to just try every possible combination of numbers in each group. We create all the possible groups and compare the sums.

Here's how the algorithm would work step-by-step:

First, figure out the total of all the numbers we have.
If the total is an odd number, we immediately know it's impossible to split them into two equal groups.
If the total is even, then we need to find a group of numbers that add up to exactly half of the total.
Start by trying to put the first number in the first group and see if there is another group possible.
Then, try putting the second number in the first group and see if there is another group possible, and so on for all remaining numbers.
Then try putting the first and second number in the first group together and see if there is another group possible, and so on for all remaining combinations.
Keep creating every possible combination of numbers for the first group.
For each combination, calculate the sum of the numbers in the first group.
If the sum of the first group is equal to half of the total, then we found a successful split and we are done. We know this is because the second group will also sum up to half of the total.
If we have tried every possible combination for the first group and none of them adds up to half of the total, then it's impossible to split the numbers into two equal groups.

Code Implementation

def can_partition_equal_subset_sum_brute_force(numbers):
    total_sum = sum(numbers)

    # If the total sum is odd, it cannot be partitioned
    if total_sum % 2 != 0:
        return False

    target_sum = total_sum // 2

    def find_subset(index, current_subset_sum):
        # If we've reached the end of the list
        if index == len(numbers):
            return current_subset_sum == target_sum

        # Check if including the current number leads to a solution
        if find_subset(index + 1, current_subset_sum + numbers[index]):
            return True

        # Check if excluding the current number leads to a solution
        if find_subset(index + 1, current_subset_sum):
            return True

        return False

    # Start the recursive search for a subset
    return find_subset(0, 0)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The described brute force approach explores all possible subsets of the input array of size n. For each element, we have two choices: include it in the first subset or exclude it. This leads to 2 * 2 * ... * 2 (n times) possible subsets. Therefore, the number of operations grows exponentially with the input size n. This results in a time complexity of O(2^n).

Space Complexity

O(2^N) – The provided brute force approach explores all possible subsets. Step 7 mentions creating every possible combination of numbers for the first group. Generating all subsets of a set of N numbers implicitly requires storing each subset. In the worst case, this would involve storing all 2^N possible subsets (or at least a significant fraction thereof during recursion). Therefore, the space complexity is O(2^N), where N is the number of elements in the input array. This space is used for managing recursive calls as it explores each possible subset combination.

Optimal Solution

Approach

The problem asks whether we can divide a collection of numbers into two groups that have the same sum. Instead of checking every possible split, we use a trick to see if a solution is even possible and then use a strategy to build one of the groups.

Here's how the algorithm would work step-by-step:

First, add up all the numbers. If the total isn't even, then it's impossible to split them into two equal groups, so we're done.
If the total is even, then we're looking for a group of numbers that adds up to exactly half of the total.
Imagine a grid where each row represents a number from our collection and each column represents a possible sum from zero up to half of the total.
We'll fill in this grid with 'yes' or 'no' to indicate whether it's possible to make that sum using the numbers we've considered so far.
Start by saying that it's always possible to make a sum of zero (by taking no numbers).
Now, for each number in our collection, go through each possible sum. For each sum, we have two choices: either include the current number or don't.
If we include the current number, then we can make the current sum if we could have made (the current sum minus the current number) using the numbers we've seen so far.
If we don't include the current number, then we can make the current sum if we could have made the current sum using only the numbers we've seen so far.
After going through all the numbers and all the sums, the answer to the original question is whether we can make the sum equal to half of the total, using all the numbers.

Code Implementation

def can_partition(numbers):    total_sum = sum(numbers)
    if total_sum % 2 != 0:
        return False
    target_sum = total_sum // 2
    number_of_numbers = len(numbers)
    # Create a DP table to store results of subproblems
    dp_table = [[False for _ in range(target_sum + 1)] for _ in range(number_of_numbers + 1)]
    # Initialize the first column to True, as a sum of 0 is always possible.
    for i in range(number_of_numbers + 1):
        dp_table[i][0] = True
    for i in range(1, number_of_numbers + 1):
        for j in range(1, target_sum + 1):
            # If current number is greater than the current sum, exclude it
            if numbers[i - 1] > j:
                dp_table[i][j] = dp_table[i - 1][j]
            else:
                # Decide whether to include the current number or not
                dp_table[i][j] = dp_table[i - 1][j] or dp_table[i - 1][j - numbers[i - 1]]
    # The result is stored in the bottom-right corner of the DP table
    return dp_table[number_of_numbers][target_sum]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*s) – The algorithm calculates the sum of the input array nums of size n. If the sum is even, it computes target s (sum / 2). Then, a 2D boolean array (or equivalent data structure) of size n x (s + 1) is implicitly constructed and iterated over. The outer loop iterates n times (for each number in nums), and the inner loop iterates s times (from 0 to target). Therefore, the time complexity is O(n*s), where n is the number of elements in the input array and s is half of the total sum.

Space Complexity

O(sum) – The described solution uses a grid (effectively a 2D array) to store boolean values representing whether a particular sum is achievable using a subset of the input numbers. The number of rows in the grid corresponds to the number of input numbers, which is implied in the plain english explanation as 'each row represents a number from our collection'. The number of columns corresponds to the target sum (half of the total sum of the input numbers). Therefore, the space required is proportional to the product of the number of input numbers and the target sum. However, since the target sum depends directly on the values of the input array, in terms of space complexity, the dominant factor is the target sum. Thus the auxiliary space required is O(sum) where sum represents half the total of the input numbers. It assumes the number of rows can be optimized, and the target sum dominates the space.

Edge Cases

Case	How to Handle
Empty input array (nums is null or nums.length == 0)	Return false immediately as an empty set cannot be partitioned into two equal subsets.
Array with only one element	Return false immediately because one element cannot be partitioned into two equal subsets unless the element is 0, which also should return false.
Sum of elements is odd (target sum is not an integer)	Return false immediately because if the sum is odd, it's impossible to divide it into two equal integer subsets.
Array contains negative numbers	The standard dynamic programming approach doesn't directly handle negative numbers, requiring a transformation or adjustment to shift all numbers to non-negative.
Array contains zero(s)	Zeros should not affect the correctness of the dynamic programming solution, but could cause inefficiencies in some approaches like recursion if not handled carefully.
Very large numbers or a very large sum leading to integer overflow	Use a larger data type (e.g., long) or modular arithmetic during sum calculations to prevent integer overflow errors.
Large input array size exceeding memory limitations	Optimize memory usage by potentially using a 1D DP array instead of a 2D array, or consider alternative algorithms if DP is impractical.
All elements are the same value.	This is a valid case, and the solution should return true if the array has an even number of elements greater than 1, and false otherwise.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array, `nums`?
Can the input array `nums` contain negative integers or zero values?
Are there any constraints on the range of values within the integer array `nums`?
If a partition is not possible, should I return `false`?
Are duplicate numbers allowed in the input array, and if so, how should they be handled?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out the total of all the numbers we have.
If the total is an odd number, we immediately know it's impossible to split them into two equal groups.
If the total is even, then we need to find a group of numbers that add up to exactly half of the total.
Start by trying to put the first number in the first group and see if there is another group possible.
Then, try putting the second number in the first group and see if there is another group possible, and so on for all remaining numbers.
Then try putting the first and second number in the first group together and see if there is another group possible, and so on for all remaining combinations.
Keep creating every possible combination of numbers for the first group.
For each combination, calculate the sum of the numbers in the first group.
If the sum of the first group is equal to half of the total, then we found a successful split and we are done. We know this is because the second group will also sum up to half of the total.
If we have tried every possible combination for the first group and none of them adds up to half of the total, then it's impossible to split the numbers into two equal groups.

Code Implementation

def can_partition_equal_subset_sum_brute_force(numbers):
    total_sum = sum(numbers)

    # If the total sum is odd, it cannot be partitioned
    if total_sum % 2 != 0:
        return False

    target_sum = total_sum // 2

    def find_subset(index, current_subset_sum):
        # If we've reached the end of the list
        if index == len(numbers):
            return current_subset_sum == target_sum

        # Check if including the current number leads to a solution
        if find_subset(index + 1, current_subset_sum + numbers[index]):
            return True

        # Check if excluding the current number leads to a solution
        if find_subset(index + 1, current_subset_sum):
            return True

        return False

    # Start the recursive search for a subset
    return find_subset(0, 0)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, add up all the numbers. If the total isn't even, then it's impossible to split them into two equal groups, so we're done.
If the total is even, then we're looking for a group of numbers that adds up to exactly half of the total.
Imagine a grid where each row represents a number from our collection and each column represents a possible sum from zero up to half of the total.
We'll fill in this grid with 'yes' or 'no' to indicate whether it's possible to make that sum using the numbers we've considered so far.
Start by saying that it's always possible to make a sum of zero (by taking no numbers).
Now, for each number in our collection, go through each possible sum. For each sum, we have two choices: either include the current number or don't.
If we include the current number, then we can make the current sum if we could have made (the current sum minus the current number) using the numbers we've seen so far.
If we don't include the current number, then we can make the current sum if we could have made the current sum using only the numbers we've seen so far.
After going through all the numbers and all the sums, the answer to the original question is whether we can make the sum equal to half of the total, using all the numbers.

Code Implementation

def can_partition(numbers):    total_sum = sum(numbers)
    if total_sum % 2 != 0:
        return False
    target_sum = total_sum // 2
    number_of_numbers = len(numbers)
    # Create a DP table to store results of subproblems
    dp_table = [[False for _ in range(target_sum + 1)] for _ in range(number_of_numbers + 1)]
    # Initialize the first column to True, as a sum of 0 is always possible.
    for i in range(number_of_numbers + 1):
        dp_table[i][0] = True
    for i in range(1, number_of_numbers + 1):
        for j in range(1, target_sum + 1):
            # If current number is greater than the current sum, exclude it
            if numbers[i - 1] > j:
                dp_table[i][j] = dp_table[i - 1][j]
            else:
                # Decide whether to include the current number or not
                dp_table[i][j] = dp_table[i - 1][j] or dp_table[i - 1][j - numbers[i - 1]]
    # The result is stored in the bottom-right corner of the DP table
    return dp_table[number_of_numbers][target_sum]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array (nums is null or nums.length == 0)	Return false immediately as an empty set cannot be partitioned into two equal subsets.
Array with only one element	Return false immediately because one element cannot be partitioned into two equal subsets unless the element is 0, which also should return false.
Sum of elements is odd (target sum is not an integer)	Return false immediately because if the sum is odd, it's impossible to divide it into two equal integer subsets.
Array contains negative numbers	The standard dynamic programming approach doesn't directly handle negative numbers, requiring a transformation or adjustment to shift all numbers to non-negative.
Array contains zero(s)	Zeros should not affect the correctness of the dynamic programming solution, but could cause inefficiencies in some approaches like recursion if not handled carefully.
Very large numbers or a very large sum leading to integer overflow	Use a larger data type (e.g., long) or modular arithmetic during sum calculations to prevent integer overflow errors.
Large input array size exceeding memory limitations	Optimize memory usage by potentially using a 1D DP array instead of a 2D array, or consider alternative algorithms if DP is impractical.
All elements are the same value.	This is a valid case, and the solution should return true if the array has an even number of elements greater than 1, and false otherwise.