Jobs

Interviews

Discussions

Partition Equal Subset Sum

Medium

Amazon

3 views

Topics:

ArraysDynamic Programming

Given an integer array nums, determine if you can partition the array into two subsets such that the sum of elements in both subsets is equal.

For example:

nums = [1, 5, 11, 5] should return true because the array can be partitioned as [1, 5, 5] and [11].
nums = [1, 2, 3, 5] should return false because the array cannot be partitioned into equal sum subsets.

Consider these constraints:

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

Explain your approach with a time and space complexity analysis. Provide code implementation in Python.

Partition Equal Subset Sum

Medium

Amazon

3 views

Topics:

ArraysDynamic Programming

Given an integer array nums, determine if you can partition the array into two subsets such that the sum of elements in both subsets is equal.

For example:

nums = [1, 5, 11, 5] should return true because the array can be partitioned as [1, 5, 5] and [11].
nums = [1, 2, 3, 5] should return false because the array cannot be partitioned into equal sum subsets.

Consider these constraints:

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

Explain your approach with a time and space complexity analysis. Provide code implementation in Python.

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:

Can the input array contain only positive integers, or can it also contain zero or negative integers?
What is the maximum size of the input array, and what is the maximum value of an integer within the array?
If it is not possible to partition the array into two subsets with equal sums, what should the function return? Should it return false, null, or throw an exception?
Are duplicate numbers allowed in the input array, and if so, how do they affect the partitioning?
If multiple valid partitions exist, is it sufficient to return `true` without needing to identify or return a specific partition?

Brute Force Solution

Approach

The brute force approach to determine if a set can be partitioned into two equal sum subsets involves exploring all possible combinations of elements. We aim to exhaustively check every possible subset and its complement. If we find one subset that sums to half the total sum, we know a partition is possible.

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

First, calculate the total sum of all the numbers in the set.
If the total sum is an odd number, we know it is impossible to split the set into two equal subsets, and we are done.
If the total sum is even, we need to find a subset that sums up to exactly half of the total sum.
Now, imagine we are building subsets, one number at a time. We'll try absolutely every possible combination of numbers.
For each number, we have a choice: either include it in our current subset, or exclude it.
So, we explore both possibilities: add the number and see what happens, and then don't add the number and see what happens.
We keep adding numbers or not, until we have considered all the numbers in the original set.
During this process, whenever a subset's sum equals half the total sum, we know we've found a successful partition.
If we exhaust all possible subsets without finding one that sums to exactly half the total sum, then a partition into equal subsets is not possible.

Code Implementation

def can_partition_equal_subset_sum(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 can_find_subset(index, current_sum):
        # If the current sum equals the target, we found a partition
        if current_sum == target_sum:
            return True

        # If the index is out of bounds or the current sum exceeds
        # the target, stop the search
        if index >= len(numbers) or current_sum > target_sum:
            return False

        # Explore both possibilities: include and exclude the current number
        include_current_number = can_find_subset(index + 1, current_sum + numbers[index])

        # Check if a partition can be found by excluding the current number.
        exclude_current_number = can_find_subset(index + 1, current_sum)

        #If either branch returned true, then short circuit and return
        return include_current_number or exclude_current_number

    # Start the recursion from the beginning
    return can_find_subset(0, 0)

Big(O) Analysis

Time Complexity

O(2^n) – The provided brute force approach explores all possible subsets of the input set. For each element in the set of size n, there are two choices: either include it in the subset or exclude it. This creates a binary tree of possible subset combinations where each level of the tree corresponds to an element in the input set. Therefore, the total number of possible subsets is 2^n. Checking each subset potentially requires summing the subset elements, however, the dominating factor is exploring all 2^n subsets, thus giving us O(2^n) time complexity.

Space Complexity

O(N) – The provided brute-force approach uses recursion to explore all possible subsets. For each number in the input set, a recursive call is made, representing the choice of including or excluding the number. This leads to a recursion tree of depth N, where N is the number of elements in the input set. Thus, the maximum depth of the call stack will be N, requiring space to store the function call frames. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The problem asks if a group of numbers can be divided into two subgroups that have the same total. The trick is to realize that if such a division is possible, each subgroup must add up to exactly half of the total sum of all the numbers. We'll use this idea to figure it out efficiently.

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

First, calculate the total sum of all the numbers in the group.
If the total sum is an odd number, we immediately know it's impossible to divide the numbers into two equal subgroups, so we're done.
If the total sum is even, then we try to figure out if we can find a subgroup of numbers that adds up to exactly half of the total sum. This is the key step.
Imagine you have a table. Each row represents a number from the original group, and each column represents a possible sum from zero up to half the total sum.
Start filling the table. At each spot, ask: 'Can I make this sum using numbers from the original group *up to this row*?'
The first row represents only the first number in the group. Check if the first number is equal to the current sum. If it is, mark the spot as 'yes' (we can make the sum). Otherwise, mark it as 'no'.
For each row after the first, we have two choices: either include the current number in our subgroup, or don't include it.
If we don't include the number, then the answer for that spot is the same as the answer from the row above (because we're ignoring the current number).
If we *do* include the number, we need to check if we could make the target sum *minus* the current number in the *previous* row. If we could, then we can make the current sum too. This is because the current number makes up the difference.
Keep filling the table like this, row by row.
After filling the entire table, look at the bottom right corner. This spot tells us whether we can make the target sum (half of the total sum) using any of the numbers in the original group. If it says 'yes', then the original group can be divided into two equal subgroups.

Code Implementation

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

    if total_sum % 2 != 0:
        return False

    target_sum = total_sum // 2

    # dp[i][j] is true if a subset of the first i elements can sum to j
    dp_table = [[False for _ in range(target_sum + 1)] for _ in range(len(numbers) + 1)]

    # An empty set can always form a sum of 0
    for i in range(len(numbers) + 1):
        dp_table[i][0] = True

    for i in range(1, len(numbers) + 1):
        for current_sum in range(1, target_sum + 1):
            #If current number is greater than current sum, exclude it
            if numbers[i-1] > current_sum:
                dp_table[i][current_sum] = dp_table[i-1][current_sum]
            else:
                # Check if sum can be obtained by including or excluding
                dp_table[i][current_sum] = (dp_table[i-1][current_sum] or
                                          dp_table[i-1][current_sum-numbers[i-1]])

    # The bottom right corner contains the answer
    return dp_table[len(numbers)][target_sum]

Big(O) Analysis

Time Complexity

O(n*s) – The algorithm computes the sum of the input array of n numbers which takes O(n) time. It then constructs a 2D table (dp) of size (n+1) x (s+1), where s is equal to half the total sum. The algorithm iterates through the table, filling each cell. The nested loop structure means we have n rows and s columns, so the algorithm processes n*s cells in total. Each cell computation takes constant time, and the initial sum calculation is dominated by the table processing, therefore the overall time complexity is O(n*s).

Space Complexity

O(S) – The dominant space usage stems from the table described in the explanation. This table has rows representing each number from the input group and columns representing possible sums from zero up to half the total sum (S/2). Therefore, the table requires space proportional to the number of rows (N, the number of input numbers) multiplied by the number of columns (S/2, where S is the total sum of the input numbers). While technically O(N * S/2), it's more commonly expressed as O(N*S) or simplified to O(S) if we assume N is constant or relatively small compared to the sum S. This assumes the table is implemented using a data structure like a 2D boolean array.

Edge Cases

Case	How to Handle
Empty input array	Return true because an empty set can be partitioned into two empty sets with equal sum (both zero).
Array with a single element	Return false, since a single element cannot be partitioned into two subsets with equal sum unless the single element itself is zero (which should return true).
Array with a very large number of elements (performance)	Dynamic programming solution should scale reasonably well to larger inputs as long as the sum does not overflow, but memoization is essential to avoid exponential time complexity.
Array with all identical numbers	If the sum is even, it's always possible; if odd, it's not.
Array containing negative numbers	This problem is defined to only use positive numbers, reject negative number inputs.
Array sum is odd (no solution possible)	Immediately return false if the sum of the array elements is odd, as an even sum is required for partitioning.
Array contains zero(s)	Zeroes do not affect the target sum, but handle edge cases for zeroes appropriately depending on whether the solution accounts for them directly or indirectly.
The sum of the array exceeds the maximum integer value	Use a data type with a larger range to store the sum, or handle the overflow condition appropriately (e.g. prevent calculation and return false).

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:

Can the input array contain only positive integers, or can it also contain zero or negative integers?
What is the maximum size of the input array, and what is the maximum value of an integer within the array?
If it is not possible to partition the array into two subsets with equal sums, what should the function return? Should it return false, null, or throw an exception?
Are duplicate numbers allowed in the input array, and if so, how do they affect the partitioning?
If multiple valid partitions exist, is it sufficient to return `true` without needing to identify or return a specific partition?

Brute Force Solution

Approach

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

First, calculate the total sum of all the numbers in the set.
If the total sum is an odd number, we know it is impossible to split the set into two equal subsets, and we are done.
If the total sum is even, we need to find a subset that sums up to exactly half of the total sum.
Now, imagine we are building subsets, one number at a time. We'll try absolutely every possible combination of numbers.
For each number, we have a choice: either include it in our current subset, or exclude it.
So, we explore both possibilities: add the number and see what happens, and then don't add the number and see what happens.
We keep adding numbers or not, until we have considered all the numbers in the original set.
During this process, whenever a subset's sum equals half the total sum, we know we've found a successful partition.
If we exhaust all possible subsets without finding one that sums to exactly half the total sum, then a partition into equal subsets is not possible.

Code Implementation

def can_partition_equal_subset_sum(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 can_find_subset(index, current_sum):
        # If the current sum equals the target, we found a partition
        if current_sum == target_sum:
            return True

        # If the index is out of bounds or the current sum exceeds
        # the target, stop the search
        if index >= len(numbers) or current_sum > target_sum:
            return False

        # Explore both possibilities: include and exclude the current number
        include_current_number = can_find_subset(index + 1, current_sum + numbers[index])

        # Check if a partition can be found by excluding the current number.
        exclude_current_number = can_find_subset(index + 1, current_sum)

        #If either branch returned true, then short circuit and return
        return include_current_number or exclude_current_number

    # Start the recursion from the beginning
    return can_find_subset(0, 0)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, calculate the total sum of all the numbers in the group.
If the total sum is an odd number, we immediately know it's impossible to divide the numbers into two equal subgroups, so we're done.
If the total sum is even, then we try to figure out if we can find a subgroup of numbers that adds up to exactly half of the total sum. This is the key step.
Imagine you have a table. Each row represents a number from the original group, and each column represents a possible sum from zero up to half the total sum.
Start filling the table. At each spot, ask: 'Can I make this sum using numbers from the original group *up to this row*?'
The first row represents only the first number in the group. Check if the first number is equal to the current sum. If it is, mark the spot as 'yes' (we can make the sum). Otherwise, mark it as 'no'.
For each row after the first, we have two choices: either include the current number in our subgroup, or don't include it.
If we don't include the number, then the answer for that spot is the same as the answer from the row above (because we're ignoring the current number).
If we *do* include the number, we need to check if we could make the target sum *minus* the current number in the *previous* row. If we could, then we can make the current sum too. This is because the current number makes up the difference.
Keep filling the table like this, row by row.
After filling the entire table, look at the bottom right corner. This spot tells us whether we can make the target sum (half of the total sum) using any of the numbers in the original group. If it says 'yes', then the original group can be divided into two equal subgroups.

Code Implementation

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

    if total_sum % 2 != 0:
        return False

    target_sum = total_sum // 2

    # dp[i][j] is true if a subset of the first i elements can sum to j
    dp_table = [[False for _ in range(target_sum + 1)] for _ in range(len(numbers) + 1)]

    # An empty set can always form a sum of 0
    for i in range(len(numbers) + 1):
        dp_table[i][0] = True

    for i in range(1, len(numbers) + 1):
        for current_sum in range(1, target_sum + 1):
            #If current number is greater than current sum, exclude it
            if numbers[i-1] > current_sum:
                dp_table[i][current_sum] = dp_table[i-1][current_sum]
            else:
                # Check if sum can be obtained by including or excluding
                dp_table[i][current_sum] = (dp_table[i-1][current_sum] or
                                          dp_table[i-1][current_sum-numbers[i-1]])

    # The bottom right corner contains the answer
    return dp_table[len(numbers)][target_sum]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return true because an empty set can be partitioned into two empty sets with equal sum (both zero).
Array with a single element	Return false, since a single element cannot be partitioned into two subsets with equal sum unless the single element itself is zero (which should return true).
Array with a very large number of elements (performance)	Dynamic programming solution should scale reasonably well to larger inputs as long as the sum does not overflow, but memoization is essential to avoid exponential time complexity.
Array with all identical numbers	If the sum is even, it's always possible; if odd, it's not.
Array containing negative numbers	This problem is defined to only use positive numbers, reject negative number inputs.
Array sum is odd (no solution possible)	Immediately return false if the sum of the array elements is odd, as an even sum is required for partitioning.
Array contains zero(s)	Zeroes do not affect the target sum, but handle edge cases for zeroes appropriately depending on whether the solution accounts for them directly or indirectly.
The sum of the array exceeds the maximum integer value	Use a data type with a larger range to store the sum, or handle the overflow condition appropriately (e.g. prevent calculation and return false).