Question

1. Given an array ? of ? integers. Divide ? into three subsets such that the total absolute difference of subset sums between them is minimum. Provide python source code, time complexity, and pseudocode. thank you

Answer 1

The problem can be solved using dynamic programming when the sum of the elements is not too big. We can create a 2D array dp[n+1][sum+1] where n is a number of elements in a given set and sum is the sum of all elements. We can construct the solution in a bottom-up manner.

The task is to divide the set into two parts.

We will consider the following factors for dividing it.

Let

dp[n+1][sum+1] = {1 if some subset from 1st to i'th has a sum

equal to j

0 otherwise}

i ranges from {1..n}

j ranges from {0..(sum of all elements)}  

So   

dp[n+1][sum+1] will be 1 if

1) The sum j is achieved including i'th item

2) The sum j is achieved excluding i'th item.

Let sum of all the elements be S.  

To find Minimum sum difference, w have to find j such

that Min{sum - j*2 : dp[n][j] == 1 }

where j varies from 0 to sum/2

The idea is, sum of S1 is j and it should be closest

to sum/2, i.e., 2*j should be closest to sum.

def findMin(a, n):

su = 0

# Calculate sum of all elements

su = sum(a)

# Create an 2d list to store

# results of subproblems

dp = [[0 for i in range(su + 1)]

for j in range(n + 1)]

# Initialize first column as true.

# 0 sum is possible

# with all elements.

for i in range(n + 1):

dp[i][0] = True

# Initialize top row, except dp[0][0],

# as false. With 0 elements, no other

# sum except 0 is possible

for j in range(1, su + 1):

dp[0][j] = False

# Fill the partition table in

# bottom up manner

for i in range(1, n + 1):

for j in range(1, su + 1):

# If i'th element is excluded

dp[i][j] = dp[i - 1][j]

# If i'th element is included

if a[i - 1] <= j

dp[i][j] |= dp[i - 1][j - a[i - 1]]

# Initialize difference

# of two sums.

diff = sys.maxsize

# Find the largest j such that dp[n][j]

# is true where j loops from sum/2 t0 0

for j in range(su // 2, -1, -1):

if dp[n][j] == True:

diff = su - (2 * j)

break

return diff

# Driver code

a = [ 3, 1, 4, 2, 2, 1 ]

n = len(a)

print("The minimum difference between "

"2 sets is ", findMin(a, n))

Time Complexity = O(n*sum) where n is the number of elements and sum is the sum of all elements.