How to divide a set into two subsets so that the difference between the sum of numbers in two sets is minimal?

Question

For a given set of numbers, divide the numbers into two subsets so that the difference between the sum of the numbers in the two subsets is minimal.

This is an idea that I have, but I'm not sure if this is the right solution:

1. Sort array
2. Take the first 2 items. Consider them as 2 sets (each of which has 1 element)
3. Take the next element from the array.
4. Decide in which set this element should go (calculating the sum => it should be minimal)
5. Reiteration

That's the right decision? Can we do better?

Answer 1

The version of the solution to the problem you are describing is an NP-complete problem and is called a separation problem . There are a number of approximations that in many cases provide optimal or at least sufficiently good solutions.

The simple algorithm that you described is the way that children choose teams. This greedy algorithm works great if the numbers in the set have the same orders.

In the article "The most difficult problem " an American scientist gives an excellent analysis of the problem. You have to go through and read it!

Answer 2

No, this does not work. There is no solution in polynomial time (if only P = NP). The best you can do is just look at all the different subsets. Take a look at the problem of the sum of the subsets .

Consider the list [0, 1, 5, 6] . You will require {0, 5} and {1, 6} when the best answer is actually {0, 1, 5} and {6} .

Answer 3

Combinations by combinations:

 import itertools as it def min_diff_sets(data): """ Parameters: - `data`: input list. Return: - min diff between sum of numbers in two sets """ if len(data) == 1: return data[0] s = sum(data) # `a` is list of all possible combinations of all possible lengths (from 1 # to len(data) ) a = [] for i in range(1, len(data)): a.extend(list(it.combinations(data, i))) # `b` is list of all possible pairs (combinations) of all elements from `a` b = it.combinations(a, 2) # `c` is going to be final correct list of combinations. # Let apply 2 filters: # 1. leave only pairs where: sum of all elements == sum(data) # 2. leave only pairs where: flat list from pairs == data c = filter(lambda x: sum(x[0])+sum(x[1])==s, b) c = filter(lambda x: sorted([i for sub in x for i in sub])==sorted(data), c) # `res` = [min_diff_between_sum_of_numbers_in_two_sets, # ((set_1), (set_2)) # ] res = sorted([(abs(sum(i[0]) - sum(i[1])), i) for i in c], key=lambda x: x[0]) return min([i[0] for i in res]) if __name__ == '__main__': assert min_diff_sets([10, 10]) == 0, "1st example" assert min_diff_sets([10]) == 10, "2nd example" assert min_diff_sets([5, 8, 13, 27, 14]) == 3, "3rd example" assert min_diff_sets([5, 5, 6, 5]) == 1, "4th example" assert min_diff_sets([12, 30, 30, 32, 42, 49]) == 9, "5th example" assert min_diff_sets([1, 1, 1, 3]) == 0, "6th example" 

Answer 4

One small change: reverse the order - start with the highest number and go down. This minimizes the error.

Answer 5

Do you sort your subset in descending order or ascending order?

Think of it this way: an array of {1, 3, 5, 8, 9, 25}

If you were divided, you would have {1,8,9} = 18 {3,5,25} = 33

If it were sorted in descending order, it would turn out much better

{25.1} = 26 {9,8,5,3} = 25

So, your decision is basically the right one, you just need to make sure that it takes the highest values ​​first.

EDIT: read tskuzzy post. Mine is not working

Answer 6

Start adding numbers, but each time compare the amount with the next number. If the sum is greater than or equal, move the number to another array.

Now, for the next numbers, it immediately shifts to another array if the new sum is <the first sum, and then you can repeat the same process on the remaining numbers. Thus, we will finish solving your problem in only one iteration.

If the array contains negative numbers above, it will not work.

Answer 7

After many thoughts and combinations, I came up with the following solution.

 1. Sort and add elements at the same time.(To reduce one more iteration on array.) 2. Do (Sum/2) and find out median of sorted array (array/2)(median can be used to optimize more) 3. Pick up highest and lowest one by one until its near or equal to (sum/2) 

This solution will work for negative values.

Answer 8

Try the following:

  partition(i, A, B) = min(partition(i+1, AUA[i], B), partition(i+1, A, BUA[i])) where i< n Absolute(Sigma(A) - Sigma(B)) where i = nn : number of elements in Original Array 

Answer 9

This is a variation of the summation problem and the subset. In the problem of the sum of the subset given by n positive integers and the value of k, we must find the sum of the subset whose value is less than or equal to k. In the above task, we defined an array, here we must find a subset whose sum is less than or equal to total_sum (the sum of the values ​​of the array). So, the sum of the subset can be found using variations of the knapsack algorithm, taking profit as the given values ​​of the array. And the final answer is total_sum-dp [n] [total_sum / 2]. See the code below for an understanding.

 #include<iostream> #include<cstdio> using namespace std; int main() { int n; cin>>n; int arr[n],sum=0; for(int i=1;i<=n;i++) cin>>arr[i],sum+=arr[i]; int temp=sum/2; int dp[n+1][temp+2]; for(int i=0;i<=n;i++) { for(int j=0;j<=temp;j++) { if(i==0 || j==0) dp[i][j]=0; else if(arr[i]<=j) dp[i][j]=max(dp[i-1][j],dp[i-1][j-arr[i]]+arr[i]); else { dp[i][j]=dp[i-1][j]; } } } cout<<sum-2*dp[n][temp]<<endl; } 

Answer 10

This can be solved using BST.
First assemble an array say arr1
To start creating another arr2 with the last element arr1 (remove this element from arr1)

Now: repeat the steps until the exchange occurs.

• Check arr1 for an element that can be moved to arr2 using BST so that diff with a difference of less than MIN is still found.
• if we find the item, move that item to arr2 and go to step 1 again.
• If we do not find any item in the above steps, follow steps 1 and 2 for arr2 and arr1. those. now check if we have any element in arr2 that can be transferred to arr1
• follow steps 1-4 until we need an exchange.
• we get the solution.

Sample Java code:

 import java.util.ArrayList; import java.util.Collections; import java.util.List; /** * Divide an array so that the difference between these 2 is min * * @author shaikhjamir * */ public class DivideArrayForMinDiff { /** * Create 2 arrays and try to find the element from 2nd one so that diff is * min than the current one */ private static int sum(List<Integer> arr) { int total = 0; for (int i = 0; i < arr.size(); i++) { total += arr.get(i); } return total; } private static int diff(ArrayList<Integer> arr, ArrayList<Integer> arr2) { int diff = sum(arr) - sum(arr2); if (diff < 0) diff = diff * -1; return diff; } private static int MIN = Integer.MAX_VALUE; private static int binarySearch(int low, int high, ArrayList<Integer> arr1, int arr2sum) { if (low > high || low < 0) return -1; int mid = (low + high) / 2; int midVal = arr1.get(mid); int sum1 = sum(arr1); int resultOfMoveOrg = (sum1 - midVal) - (arr2sum + midVal); int resultOfMove = (sum1 - midVal) - (arr2sum + midVal); if (resultOfMove < 0) resultOfMove = resultOfMove * -1; if (resultOfMove < MIN) { // lets do the swap return mid; } // this is positive number greater than min // which mean we should move left if (resultOfMoveOrg < 0) { // 1,10, 19 ==> 30 // 100 // 20, 110 = -90 // 29, 111 = -83 return binarySearch(low, mid - 1, arr1, arr2sum); } else { // resultOfMoveOrg > 0 // 1,5,10, 15, 19, 20 => 70 // 21 // For 10 // 60, 31 it will be 29 // now if we move 1 // 71, 22 ==> 49 // but now if we move 20 // 50, 41 ==> 9 return binarySearch(mid + 1, high, arr1, arr2sum); } } private static int findMin(ArrayList<Integer> arr1) { ArrayList<Integer> list2 = new ArrayList<>(arr1.subList(arr1.size() - 1, arr1.size())); arr1.remove(arr1.size() - 1); while (true) { int index = binarySearch(0, arr1.size(), arr1, sum(list2)); if (index != -1) { int val = arr1.get(index); arr1.remove(index); list2.add(val); Collections.sort(list2); MIN = diff(arr1, list2); } else { // now try for arr2 int index2 = binarySearch(0, list2.size(), list2, sum(arr1)); if (index2 != -1) { int val = list2.get(index2); list2.remove(index2); arr1.add(val); Collections.sort(arr1); MIN = diff(arr1, list2); } else { // no switch in both the cases break; } } } System.out.println("MIN==>" + MIN); System.out.println("arr1==>" + arr1 + ":" + sum(arr1)); System.out.println("list2==>" + list2 + ":" + sum(list2)); return 0; } public static void main(String args[]) { ArrayList<Integer> org = new ArrayList<>(); org = new ArrayList<>(); org.add(1); org.add(2); org.add(3); org.add(7); org.add(8); org.add(10); findMin(org); } } 

Answer 11

A recursive approach is to generate all possible sums from all array values ​​and check which solution is the most optimal. To generate the amounts, we either include the ith element in set 1 or do not include, i.e. include in set 2.

The time complexity is O (n * sum) for both time and space. T

 public class MinimumSubsetSum { static int dp[][]; public static int minDiffSubsets(int arr[], int i, int calculatedSum, int totalSum) { if(dp[i][calculatedSum] != -1) return dp[i][calculatedSum]; /** * If i=0, then the sum of one subset has been calculated as we have reached the last * element. The sum of another subset is totalSum - calculated sum. We need to return the * difference between them. */ if(i == 0) { return Math.abs((totalSum - calculatedSum) - calculatedSum); } //Including the ith element int iElementIncluded = minDiffSubsets(arr, i-1, arr[i-1] + calculatedSum, totalSum); //Excluding the ith element int iElementExcluded = minDiffSubsets(arr, i-1, calculatedSum, totalSum); int res = Math.min(iElementIncluded, iElementExcluded); dp[i][calculatedSum] = res; return res; } public static void util(int arr[]) { int totalSum = 0; int n = arr.length; for(Integer e : arr) totalSum += e; dp = new int[n+1][totalSum+1]; for(int i=0; i <= n; i++) for(int j=0; j <= totalSum; j++) dp[i][j] = -1; int res = minDiffSubsets(arr, n, 0, totalSum); System.out.println("The min difference between two subset is " + res); } public static void main(String[] args) { util(new int[]{3, 1, 4, 2, 2, 1}); } } 

Answer 12

No, your algorithm is incorrect. Your algorithm follows a greedy approach. I implemented your approach and it did not pass this test case: (You can try here )

Greedy algorithm:

 #include<bits/stdc++.h> #define rep(i,_n) for(int i=0;i<_n;i++) using namespace std; #define MXN 55 int a[MXN]; int main() { //code int t,n,c; cin>>t; while(t--){ cin>>n; rep(i,n) cin>>a[i]; sort(a, a+n); reverse(a, a+n); ll sum1 = 0, sum2 = 0; rep(i,n){ cout<<a[i]<<endl; if(sum1<=sum2) sum1 += a[i]; else sum2 += a[i]; } cout<<abs(sum1-sum2)<<endl; } return 0; } 

Precedent:

 1 8 16 14 13 13 12 10 9 3 Wrong Ans: 6 16 13 10 9 14 13 12 3 Correct Ans: 0 16 13 13 3 14 12 10 9 

The reason the greedy algorithm fails is because it does not take into account cases where taking a larger element in the current set of large sums, and later a much smaller one in the set of large sums, can lead to much better results. He always tries to minimize the current difference without exploring and not knowing additional features, while in the right solution you can include an element in a larger set and include a much smaller element later to compensate for this difference, as in the previous test example.

The right decision:

To understand the solution, you need to understand all of the problems listed below in order:

• Dynamic Programming Backpack 0/1
• Sum of an equal subset of a partition with DP
• Decision

My code (same logic as this one ):

 #include<bits/stdc++.h> #define rep(i,_n) for(int i=0;i<_n;i++) using namespace std; #define MXN 55 int arr[MXN]; int dp[MXN][MXN*MXN]; int main() { //code int t,N,c; cin>>t; while(t--){ rep(i,MXN) fill(dp[i], dp[i]+MXN*MXN, 0); cin>>N; rep(i,N) cin>>arr[i]; int sum = accumulate(arr, arr+N, 0); dp[0][0] = 1; for(int i=1; i<=N; i++) for(int j=sum; j>=0; j--) dp[i][j] |= (dp[i-1][j] | (j>=arr[i-1] ? dp[i-1][j-arr[i-1]] : 0)); int res = sum; for(int i=0; i<=sum/2; i++) if(dp[N][i]) res = min(res, abs(i - (sum-i))); cout<<res<<endl; } return 0; } 

Answer 13

 int ModDiff(int a, int b) { if(a < b)return b - a; return ab; } int EqDiv(int *a, int l, int *SumI, int *SumE) { static int tc = 0; int min = ModDiff(*SumI,*SumE); for(int i = 0; i < l; i++) { swap(a,0,i); a++; int m1 = EqDiv(a, l-1, SumI,SumE); a--; swap(a,0,i); *SumI = *SumI + a[i]; *SumE = *SumE - a[i]; swap(a,0,i); a++; int m2 = EqDiv(a,l-1, SumI,SumE); a--; swap(a,0,i); *SumI = *SumI - a[i]; *SumE = *SumE + a[i]; min = min3(min,m1,m2); } return min; 

}

call the function with SumI = 0 and SumE = sumof all the elements in a. This solution O (n!) Computes a way to split a given array into two parts, so the difference is minimal. But definitely not practical because of n! time complexity aimed at improving this with DP.

Answer 14

Please check this logic that I wrote for this problem. It worked for several scenarios that I tested. Please comment on the solution, Approach:

• Sort the main array and divide it into 2 teams.
• Then start making the command equal in changing and replacing elements from one array to another, based on the conditions mentioned in the code.

If the difference in the difference in the amounts is less than the minimum number of a larger array (an array with a larger sum), then the offset of the elements from the larger array to the smaller array. The change occurs with the condition, this element is from a larger array with a value less than or equal to the difference. When all elements from the larger array are larger than the difference, the switch stops and swaps. I just replace the last elements of the array (it can be made more efficient by finding which two elements will be replaced), but still it worked. Let me know if this logic failed anyway.

 public class SmallestDifference { static int sum1 = 0, sum2 = 0, diff, minDiff; private static List<Integer> minArr1; private static List<Integer> minArr2; private static List<Integer> biggerArr; /** * @param args */ public static void main(String[] args) { SmallestDifference sm = new SmallestDifference(); Integer[] array1 = { 2, 7, 1, 4, 5, 9, 10, 11 }; List<Integer> array = new ArrayList<Integer>(); for (Integer val : array1) { array.add(val); } Collections.sort(array); CopyOnWriteArrayList<Integer> arr1 = new CopyOnWriteArrayList<>(array.subList(0, array.size() / 2)); CopyOnWriteArrayList<Integer> arr2 = new CopyOnWriteArrayList<>(array.subList(array.size() / 2, array.size())); diff = Math.abs(sm.getSum(arr1) - sm.getSum(arr2)); minDiff = array.get(0); sm.updateSum(arr1, arr2); System.out.println(arr1 + " : " + arr2); System.out.println(sum1 + " - " + sum2 + " = " + diff + " : minDiff = " + minDiff); int k = arr2.size(); biggerArr = arr2; while (diff != 0 && k >= 0) { while (diff != 0 && sm.findMin(biggerArr) < diff) { sm.swich(arr1, arr2); int sum1 = sm.getSum(arr1), sum2 = sm.getSum(arr2); diff = Math.abs(sum1 - sum2); if (sum1 > sum2) { biggerArr = arr1; } else { biggerArr = arr2; } if (minDiff > diff || sm.findMin(biggerArr) > diff) { minDiff = diff; minArr1 = new CopyOnWriteArrayList<>(arr1); minArr2 = new CopyOnWriteArrayList<>(arr2); } sm.updateSum(arr1, arr2); System.out.println("Shifting : " + sum1 + " - " + sum2 + " = " + diff + " : minDiff = " + minDiff); } while (k >= 0 && minDiff > array.get(0) && minDiff != 0) { sm.swap(arr1, arr2); diff = Math.abs(sm.getSum(arr1) - sm.getSum(arr2)); if (minDiff > diff) { minDiff = diff; minArr1 = new CopyOnWriteArrayList<>(arr1); minArr2 = new CopyOnWriteArrayList<>(arr2); } sm.updateSum(arr1, arr2); System.out.println("Swapping : " + sum1 + " - " + sum2 + " = " + diff + " : minDiff = " + minDiff); k--; } k--; } System.out.println(minArr1 + " : " + minArr2 + " = " + minDiff); } private void updateSum(CopyOnWriteArrayList<Integer> arr1, CopyOnWriteArrayList<Integer> arr2) { SmallestDifference sm1 = new SmallestDifference(); sum1 = sm1.getSum(arr1); sum2 = sm1.getSum(arr2); } private int findMin(List<Integer> biggerArr2) { Integer min = biggerArr2.get(0); for (Integer integer : biggerArr2) { if(min > integer) { min = integer; } } return min; } private int getSum(CopyOnWriteArrayList<Integer> arr) { int sum = 0; for (Integer val : arr) { sum += val; } return sum; } private void swap(CopyOnWriteArrayList<Integer> arr1, CopyOnWriteArrayList<Integer> arr2) { int l1 = arr1.size(), l2 = arr2.size(), temp2 = arr2.get(l2 - 1), temp1 = arr1.get(l1 - 1); arr1.remove(l1 - 1); arr1.add(temp2); arr2.remove(l2 - 1); arr2.add(temp1); System.out.println(arr1 + " : " + arr2); } private void swich(CopyOnWriteArrayList<Integer> arr1, CopyOnWriteArrayList<Integer> arr2) { Integer e; if (sum1 > sum2) { e = this.findElementJustLessThanMinDiff(arr1); arr1.remove(e); arr2.add(e); } else { e = this.findElementJustLessThanMinDiff(arr2); arr2.remove(e); arr1.add(e); } System.out.println(arr1 + " : " + arr2); } private Integer findElementJustLessThanMinDiff(CopyOnWriteArrayList<Integer> arr1) { Integer e = arr1.get(0); int tempDiff = diff - e; for (Integer integer : arr1) { if (diff > integer && (diff - integer) < tempDiff) { e = integer; tempDiff = diff - e; } } return e; } 

}

Answer 15

A possible solution here is https://stackoverflow.com/a/166707/ ... This Java program seems to solve this problem, if one condition is met - there is one and only solution to the problem.

Answer 16

 #include<bits/stdc++.h> using namespace std; bool ison(int i,int x) { if((i>>x) & 1)return true; return false; } int main() { // cout<<"enter the number of elements : "; int n; cin>>n; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; int sumarr1[(1<<n)-1]; int sumarr2[(1<<n)-1]; memset(sumarr1,0,sizeof(sumarr1)); memset(sumarr2,0,sizeof(sumarr2)); int index=0; vector<int>v1[(1<<n)-1]; vector<int>v2[(1<<n)-1]; for(int i=1;i<(1<<n);i++) { for(int j=0;j<n;j++) { if(ison(i,j)) { sumarr1[index]+=a[j]; v1[index].push_back(a[j]); } else { sumarr2[index]+=a[j]; v2[index].push_back(a[j]); } }index++; } int ans=INT_MAX; int ii; for(int i=0;i<index;i++) { if(abs(sumarr1[i]-sumarr2[i])<ans) { ii=i; ans=abs(sumarr1[i]-sumarr2[i]); } } cout<<"first partitioned array : "; for(int i=0;i<v1[ii].size();i++) { cout<<v1[ii][i]<<" "; } cout<<endl; cout<<"2nd partitioned array : "; for(int i=0;i<v2[ii].size();i++) { cout<<v2[ii][i]<<" "; } cout<<endl; cout<<"minimum difference is : "<<ans<<endl; } 

Answer 17

Many answers are mentioned about getting an “approximate” solution in a very acceptable time frame. But since he was asked in the interview, I do not think that they need an approximation algorithm. Nor do I expect them to need a naive exponential algorithm either.

Coming to a problem, assuming that the maximum value of the sum of numbers is known, it can be solved in polynomial time using dynamic programming. Link to this link https://people.cs.clemson.edu/~bcdean/dp_practice/dp_4.swf

Answer 18

 HI I think This Problem can be solved in Linear Time on a sorted array , no Polynomial Time is required , rather than Choosing Next Element u can choose nest two Element and decide which side which element to go. in This Way in this way minimize the difference, let suppose {0,1,5,6} , choose {0,1} {0} , {1} choose 5,6 {0,6}, {1,5} but still that is not exact solution , now at the end there will be difference of sum in 2 array let suppose x but there can be better solution of difference of (less than x) for that Find again 1 greedy approach over sorted half sized array and move x/2(or nearby) element from 1 set to another or exchange element of(difference x/2) so that difference can be minimized***