Problem definition : Array partition problem
Given an array of positive integers, divide it into three disjoint subsets having equal sum. These disjoint sets cover the complete array.
Example Input: [7, 6, 1, 7] Output: [[7], [6, 1], [7]]
Input: [7, 6, 2, 7] Output: Not possible to partition in three parts
Input: [[1, 1, 1, 1, 3, 2 ] Output:[[1, 1, 1], [1, 2], [3]]
Solution Brute force solution of examining all possible subsets in iterative approach.
# Gets all possible subsets of input_array which doesn't include element from skip_indices
def get_subsets(input_array, skip_indices=[]):
def get_incremental_subsets(index, subsets):
new_subsets = []
new_subsets.append([index])
for count in range(len(subsets)):
current_subset = subsets[count].copy()
current_subset.append(index)
if len(current_subset) == 1:
new_subsets.append([current_subset])
else:
new_subsets.append(current_subset)
return subsets + new_subsets
subsets = []
for count in range(len(input_array)):
if count not in skip_indices:
subsets = get_incremental_subsets(count, subsets)
return subsets
# Sum of a subset
def get_subset_sum(input_array, subset_indices):
subset_sum = 0
for subset_index in subset_indices:
subset_sum = subset_sum + input_array[subset_index]
return subset_sum
# Find partition input_array in two subsets such that each subset have sum equal to sum_value.
# Subset exclude elements present in skip_indices
def partition_two(input_array, skip_indices, sum_value):
input_array_sum = sum(input_array)
for index in skip_indices:
input_array_sum = input_array_sum - input_array[index]
if input_array_sum != 2*sum_value:
return None
subsets = get_subsets(input_array, skip_indices)
for index in range(len(subsets)):
if get_subset_sum(input_array, subsets[index]) == sum_value:
return subsets[index]
return None
def partition_three(input_array):
# Check if input_array sum is actually multiple of 3
input_array_sum = sum(input_array)
if input_array_sum%3 != 0:
return None
target_sum = input_array_sum/3
#Iterate over all subsets
for subset in get_subsets(input_array):
# Skip subsets where sum is not equal to target_sum
if get_subset_sum(input_array, subset) != target_sum:
continue
# If subset with target_sum is found, try finding two subsets with target_sum in remaining array
subset_1 = partition_two(input_array, subset, target_sum)
if subset_1 != None:
return [subset,\
subset_1,\
list(set([index for index in range(len(input_array))]) - set(subset) - set(subset_1))]
return None
print(partition_three([1, 1, 1 ])) # Possible. Subset indices are [[0], [1], [2]]
print(partition_three([1, 1, 1, 3, 2, 1 ])) # Possible. Subset indices are [[0, 1, 2], [3], [4, 5]]
print(partition_three([1, 1, 1, 1, 3, 2 ])) # Possible. Subset indices are [[0, 1, 2], [4], [3, 5]]
print(partition_three([1, 5 ])) # Not possible
print(partition_three([])) # Not possible
print(partition_three([7, 3, 2, 1, 5, 4, 8 ])) # Possible. Subset indices are [[0, 1], [3, 4, 5], [2, 6]
print(partition_three([1, 3, 6, 2, 7, 1, 2, 8 ])) # Possible. Subset indices are [[0, 1, 2], [3, 4, 5], [6, 7]]
print(partition_three([7, 6, 1, 7 ])) #Possible. Subset indices are [[0], [1, 2], [3]]
print(partition_three([7, 6, 2, 7 ])) # Not possible
print(partition_three([17, 17, 17, 34, 34, 34, 59, 59, 59])) # Possible. Subset indices are [[0, 3, 6], [1, 4, 7], [8, 2, 5]]
print(partition_three([20, 23, 25, 30, 49, 45, 27, 30, 30, 40, 22, 19])) # Possible. Subset indices are [[0, 2, 3, 5], [1, 6, 7, 9], [8, 10, 11, 4]]
Review ask
- Functional correctness
- Algorithm improvements
- Python usage