Learn to Code
John F. Dumas

Python - Array Partitioning

► Problem Description: For this problem, you'll write a function that accepts an array of integers of arbitrary length. Your function's objective is to partition the array into two subsets such that the sum of the numbers in each subset is the same. Here is an example:

array = { 1, 2, 8, 6, 3, 4 }

If we were to break 'array' up into the following two subsets:

part1 = { 2, 4, 6 }
part2 = { 1, 3, 8 }

We can see that the sum of the numbers in each subset is the same:

part1 = { 2, 4, 6 } -> ( 2 + 4 + 6 ) -> 12
part2 = { 1, 3, 8 } -> ( 1 + 3 + 8 ) -> 12

Your function should output the two subsets of the original along with their common sum if it is possible to find a solution to this problem. In some cases, there will be multiple solutions, your function only needs to show the first one it finds.

Alternatively, if it is not possible to divide the original array into two subsets with identical sums, the function should display a message to that effect. Below are some examples you can use to test your program:

► Example Output:

-----------
Example One
-----------

array: { 36, 12, 36, 25, 26, 49, 39, 5 }

first : { 26, 49, 39 }
second: { 36, 12, 36, 25, 5 }

sum: 114

-----------
Example Two
-----------

array: { 44, 48, 45, 47, 8, 39, 2, 27, 47, 4, 42 }

No partitions found

-------------
Example Three
-------------

array: { 40, 37, 41, 41, 31, 47, 5, 49, 37, 6 }

first : { 41, 31, 47, 5, 37, 6 }
second: { 40, 37, 41, 49 }

sum: 167

------------
Example Four
------------

array: { 14, 7, 34, 40, 24, 33, 25, 46, 4, 1, 46 }

first : { 40, 46, 4, 1, 46 }
second: { 14, 7, 34, 24, 33, 25 }

sum: 137

------------
Example Five
------------

array: { 26, 27, 2, 2, 6, 37, 4, 29, 10, 8 }

No partitions found

-------------
Example Six
-------------

array: { 16, 25, 31, 23, 30, 23, 12, 24, 19, 21, 27, 11, 28, 20 }

first : { 23, 12, 24, 21, 27, 28, 20 }
second: { 16, 25, 31, 23, 30, 19, 11 }

sum: 155

-------------
Example Seven
-------------

array: { 5, 22, 19, 11, 25, 25, 2, 14, 18, 24, 4, 43, 28 }

first : { 25, 24, 43, 28 }
second: { 5, 22, 19, 11, 25, 2, 14, 18, 4 }

sum: 120

-------------
Example Eight
-------------

array: { 47, 49, 45, 32, 41, 18, 7, 2, 49, 48, 18 }

first : { 45, 18, 49, 48, 18 }
second: { 47, 49, 32, 41, 7, 2 }

sum: 178

-------------
Example Nine
-------------

array: { 46, 44, 12, 29, 35, 24, 43, 17, 23, 12, 38, 6, 5 }

first : { 35, 43, 17, 23, 38, 6, 5 }
second: { 46, 44, 12, 29, 24, 12 }

sum: 167

-------------
Example Ten
-------------

array: { 10, 29, 10, 4, 29, 38, 23, 37, 14, 47, 23, 16 }

first : { 4, 38, 37, 14, 47 }
second: { 10, 29, 10, 29, 23, 23, 16 }

sum: 140

► Source Code

© John F. Dumas | johnfdumas@gmail.com | main page | top of page