Partition Equal Subset Sum
Statement
Given a non-empty array of positive integers, determine if the array can be divided into two subsets so that the sum of both subsets is equal.
Constraints
- 1 ≤
numbers.length()≤ 200 - 1 ≤
numbers[i]≤ 100
Solution
"""
production algorithm
"""
class Solution:
def can_partition_array(self, numbers):
"""
time complexity O(nk)
space complexity O(nk)
"""
if sum(numbers) % 2 == 1:
return False
k = sum(numbers) // 2
n = len(numbers)
memo = [[True if c == 0 else False if m ==
0 else None for c in range(k + 1)] for m in range(n + 1)]
for m in range(1, n + 1):
for c in range(1, k + 1):
if numbers[m - 1] <= c:
memo[m][c] = memo[m - 1][c - numbers[m - 1]] or \
memo[m - 1][c]
else:
memo[m][c] = memo[m - 1][c]
return memo[n][k]"""
unit tests
"""
from unittest import TestCase
from algorithms.dynamic_programming.partition_equal_subset_sum.solution import Solution
class SolutionTestCase(TestCase):
def test_odd_sum_nonexistent_solution(self):
# Given
numbers = [20, 17, 24, 15, 21, 22, 17, 19]
solution = Solution()
# When
actual = solution.can_partition_array(numbers)
# Then
expected = False
self.assertEqual(actual, expected)
def test_even_sum_nonexistent_solution(self):
# Given
numbers = [2, 2, 2, 4, 6, 6, 8, 8]
solution = Solution()
# When
actual = solution.can_partition_array(numbers)
# Then
expected = False
self.assertEqual(actual, expected)
def test_even_sum_existent_solution(self):
# Given
numbers = [20, 17, 24, 15, 21, 22, 16, 19]
solution = Solution()
# When
actual = solution.can_partition_array(numbers)
# Then
expected = True
self.assertEqual(actual, expected)Strategy
Dynamic Programming.
Explanation
A 2-D matrix, whose dimensions are the number of integers and their sum, is maintained to hold the optimal solution to the problem for the number of integers and their sum seen so far. In the trivial case, when the sum is 0, then the optimal solution is true, otherwise if the number of integers is 0, then the optimal solution is false.
Next, iteration of the number of integers and their sum occurs. The optimal solution for a smaller number of integers and their sum is used to find the optimal solution for a larger number of integers and their sum. Iteration ends when the optimal solution has been found for the input number of integers and their sum.
Notice, that the problem has optimal substructure, i.e. the optimal solution of a larger number of integers and their sum can be found from the optimal solution of a smaller number of integers and their sum. Also notice, that the problem has overlapping subproblems, i.e. the optimal solution of a smaller number of integers and their sum can be reused to find the optimal solution of distinct larger numbers of integers and their sums. Since the problem has optimal substructure and overlapping subproblems, then dynamic programming can be used to solve the problem.
Time Complexity
Iteration of the number of integers and their sum has time complexity O(nk). Therefore, the time complexity of the algorithm is O(nk).
Spaced Complexity
The auxiliary space complexity depends on the size of the matrix which is n × k. Therefore, the auxiliary space complexity of the algorithm is O(nk).
