I have two arrays of integers. I am looking for an algorithm to balance the sums of the numbers of the two arrays (as accurately as possible) on both arrays.

The numbers should be distributed between the arrays in such a way that there is an equilibrium and both arrays have the same sum of numbers. If no distribution is possible, the difference should be output.

Finally, the number values in both arrays should be the same (not the number of integers). In the case shown, the solution is simple because only one number needs to be moved. However, there are also complicated cases where numbers have to be shifted in "both directions" to create an equilibrium.

What would be the best solution here?

Many thanks in advance.

CodePudding user response：

• Just make a single array and fill both array values in it.
• Use Partition Equal Subset Sum.

Solution -1: (If you only want to check is it possible or not then use this)

def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if(total%2 == 1):
            return False
        size = len(nums)
        amount= total//2
        m = 1
        for n in nums:
            m |= (m << n)
        return (m >> amount) & 1

Solution -2: (If you want array values just update the logic of below code)

def canPartition(self, nums: List[int]) -> bool:
    total = sum(nums)
    if(total%2 == 1):
        return False
    size = len(nums)
    amount= total//2
    total = [False for i in range(amount 1)]
    total[0] = True
    for j in nums:
        for i in range(amount,j-1,-1):
            if(i-j >=0):
                if(total[i-j]):
                    total[i] = True
    if(total[amount] == False):
        return False
    else:
        return total[amount]