Problem No 4

"""You have been given a set of n integers. You need to write a program that will divide the set in two subsets of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible.
Note: n is even, hence sizes of two subsets must be strictly n/2

For example,

Input = {3, 4, 5, 3, 100, 1, 83, 54, 23, 20}
Output = {4, 100, 1, 23, 20} and {3, 5, 3, 83, 54}.
Both output subsets are of size 5 and sum of elements in both subsets is same (148 and 148)."""

def findMinRec(arr, i, sumCalculated,

           sumTotal):



if (i == 0):

    return abs((sumTotal - sumCalculated) -

               sumCalculated)


return min(findMinRec(arr, i - 1,

                      sumCalculated+arr[i - 1],

                      sumTotal),

           findMinRec(arr, i - 1,

                      sumCalculated, sumTotal))

def findMin(arr, n):

sumTotal = 0

for i in range(n):

    sumTotal += arr[i]




return findMinRec(arr, n,

                  0, sumTotal)

if name == "main":

arr = [3,4,5,3,100,1,83,54,23,20]

n = len(arr)

print("The minimum difference " +

      "between two sets is ",

      findMin(arr, n))