Given a set of numbers, divide the numbers into two subsets such that difference between the sum of numbers in two subsets is minimal.
This is the idea that I have, but I am not sure if this is a correct solution:
Is this the correct solution? Can we do better?
The decision version of the problem you are describing is an NP-complete problem and it is called the partition problem. There are a number of approximations which provide, in many cases, optimal or, at least, good enough solutions.
The simple algorithm you described is a way playground kids would pick teams. This greedy algorithm performs remarkably well if the numbers in the set are of similar orders of magnitude.
The article The Easiest Hardest Problem, by American Scientist, gives an excellent analysis of the problem. You should go through and read it!
No, that doesn't work. There is no polynomial time solution (unless P=NP). The best you can do is just look at all different subsets. Have a look at the subset sum problem.
Consider the list [0, 1, 5, 6]. You will claim {0, 5} and {1, 6}, when the best answer is actually {0, 1, 5} and {6}.
No, Your algorithm is wrong. Your algo follows a greedy approach. I implemented your approach and it failed over this test case: (You may try here)
A 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;
}
Test case:
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 greedy algorithm fails is that it does not consider cases when taking a larger element in current larger sum set and later a much smaller in the larger sum set may result much better results. It always try to minimize current difference without exploring or knowing further possibilities, while in a correct solution you might include an element in a larger set and include a much smaller element later to compensate this difference, same as in above test case.
Correct Solution:
To understand the solution, you will need to understand all below problems in order:
My Code (Same logic as this):
#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;
}
Combinations over combinations approach:
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's 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"
The recursive approach is to generate all possible sums from all the values of array and to check which solution is the most optimal one. To generate sums we either include the i’th item in set 1 or don’t 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});
}
}
We can use Dynamic Programming (similar to the way we find if a set can be partitioned into two equal sum subsets). Then we find the max possible sum, which will be our first partition. Second partition will be the difference of the total sum and firstSum. Answer will be the difference of the first and second partitions.
public int minDiffernce(int set[]) {
int sum = 0;
int n = set.length;
for(int i=0; i<n; i++)
sum+=set[i];
//finding half of total sum, because min difference can be at max 0, if one subset reaches half
int target = sum/2;
boolean[][] dp = new boolean[n+1][target+1];//2
for(int i = 0; i<=n; i++)
dp[i][0] = true;
for(int i= 1; i<=n; i++){
for(int j = 1; j<=target;j++){
if(set[i-1]>j) dp[i][j] = dp[i-1][j];
else dp[i][j] = dp[i-1][j] || dp[i-1][j-set[i-1]];
}
}
// we now find the max sum possible starting from target
int firstPart = 0;
for(int j = target; j>=0; j--){
if(dp[n][j] == true) {
firstPart = j; break;
}
}
int secondPart = sum - firstPart;
return Math.abs(firstPart - secondPart);
}
Perhaps you are talking about this.
I did it using MEET IN THE MIDDLE APPROACH. Its an optimization technique which works by splitting the array in two parts and then generating the subsets.
Code , feel free to ask if any queries
class Solution{
public:
void generate(vector<int> &arr, int curr, int n, int sum, vector<vector<pair<int,vector<int>>>> &store, vector<int> build){
if(curr==n){
int sz=build.size();
store[sz].push_back({sum,build});
return;
}
build.push_back(curr);
generate(arr,curr+1,n,sum+arr[curr],store,build);
build.pop_back();
generate(arr,curr+1,n,sum,store,build);
}
static bool cmp(pair<int,vector<int>> &p1, pair<int,vector<int>> &p2){
return p1.first<p2.first;
}
int BINRY_SRCH(vector<pair<int,vector<int>>> &arr, int target){
int res=-1;
int low=0;
int high=arr.size()-1;
while(low<=high){
int mid=(low+high)/2;
if(arr[mid].first>=target){
res=mid;
high=mid-1;
}
else{
low=mid+1;
}
}
return res;
}
vector<vector<int>> minDifference(vector<int>& arr, int n){
int extra=(n%2!=0);
vector<vector<pair<int,vector<int>>>> part1(n/2+1+extra);
vector<vector<pair<int,vector<int>>>> part2(n/2+1);
generate(arr,0,n/2+extra,0,part1,{});
generate(arr,n/2+extra,n,0,part2,{});
for(auto &c: part2){
sort(c.begin(),c.end(),cmp);
}
vector<vector<int>> res(2);
int diff=INT_MAX;
int sum=accumulate(arr.begin(),arr.end(),0);
for(int ele=1;ele<=n/2+extra;ele++){ // making a single subset
vector<pair<int,vector<int>>> P1=part1[ele];
vector<pair<int,vector<int>>> P2=part2[n/2+extra-ele];
for(auto x: P1){
int index=BINRY_SRCH(P2,sum/2-x.first);
if(index!=-1){
int subset1_Sum=x.first+P2[index].first;
int subset2_Sum=sum-subset1_Sum;
if(abs(subset1_Sum-subset2_Sum)<diff){
diff=abs(subset1_Sum-subset2_Sum);
vector<int> subset1=x.second;
for(auto c: P2[index].second){
subset1.push_back(c);
}
res[0]=subset1;
}
}
if(index>0){
index--;
int subset1_Sum=x.first+P2[index].first;
int subset2_Sum=sum-subset1_Sum;
if(abs(subset1_Sum-subset2_Sum)<diff){
diff=abs(subset1_Sum-subset2_Sum);
vector<int> subset1=x.second;
for(auto c: P2[index].second){
subset1.push_back(c);
}
res[0]=subset1;
}
}
}
}
vector<bool> vis(n,false);
for(int i=0;i<res[0].size();i++){
vis[res[0][i]]=true;
res[0][i]=arr[res[0][i]];
}
vector<int> subset2;
for(int i=0;i<n;i++){
if(vis[i]==false){
subset2.push_back(arr[i]);
}
}
res[1]=subset2;
// for(auto c: res[0]){
// cout<<c<<" ";
// }
// cout<<endl;
// for(auto c: res[1]){
// cout<<c<<" ";
// }
// cout<<endl;
return res;
}
};
CODE BY RAINX, ABHIJIT ROY, NIT AGARTALA
This is a variation of the knapsack and subset sum problem. In subset sum problem, given n positive integers and a value k and we have to find the sum of subset whose value is less than or equal to k. In the above problem we have given an array, here we have to find the subset whose sum is less than or equal to total_sum(sum of array values). So the subset sum can be found using a variation in knapsack algorithm,by taking profits as given array values. And the final answer is total_sum-dp[n][total_sum/2]. Have a look at the below code for clear 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;
}
This can be solve using BST.
First sort the array say arr1
To start create another arr2 with the last element of arr1 (remove this ele from arr1)
Now:Repeat the steps till no swap happens.
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);
}
}
you can use bits to solve this problem by looping over all the possible combinations using bits: main algorithm:
for(int i = 0; i < 1<<n; i++) {
int s = 0;
for(int j = 0; j < n; j++) {
if(i & 1<<j) s += arr[j];
}
int curr = abs((total-s)-s);
ans = min(ans, curr);
}
use long long for greater inputs.
but here I found a recursive and dynamic programming solution and I used both the approaches to solve the question and both worked for greater inputs perfectly fine. Hope this helps :) link to solution
One small change: reverse the order - start with the largest number and work down. This will minimize the error.
Are you sorting your subset into decending order or ascending order?
Think about it like this, the array {1, 3, 5, 8, 9, 25}
if you were to divide, you would have {1,8,9} =18 {3,5,25} =33
If it were sorted into descending order it would work out a lot better
{25,1}=26 {9,8,5,3}=25
So your solution is basically correct, it just needs to make sure to take the largest values first.
EDIT: Read tskuzzy's post. Mine does not work
Please check this logic which I have written for this problem. It worked for few scenarios I checked. Please comment on the solution, Approach :
If the difference is difference of sum is less than the minimum number of the larger array(array with bigger sum), then shift the elements from the bigger array to smaller array.Shifting happens with the condition, that element from the bigger array with value less than or equal to the difference.When all the elements from the bigger array is greater than the difference, the shifting stops and swapping happens. I m just swapping the last elements of the array (It can be made more efficient by finding which two elements to swap), but still this worked. Let me know if this logic failed in any scenario.
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;
}
}
A possible solution here- https://stackoverflow.com/a/31228461/4955513 This Java program seems to solve this problem, provided one condition is fulfilled- that there is one and only one solution to the problem.
I'll convert this problem to subset sum problem
let's take array int[] A = { 10,20,15,5,25,33 };
it should be divided into {25 20 10} and { 33 20 } and answer is 55-53=2
Notations : SUM == sum of whole array
sum1 == sum of subset1
sum2 == sum of subset1
step 1: get sum of whole array SUM=108
step 2: whichever way we divide our array into two part one thing will remain true
sum1+ sum2= SUM
step 3: if our intention is to get minimum sum difference then sum1 and sum2 should be near SUM/2 (example sum1=54 and sum2=54 then diff=0 )
steon 4: let's try combinations
sum1 = 54 AND sum2 = 54 (not possible to divide like this)
sum1 = 55 AND sum2 = 53 (possible and our solution, should break here)
sum1 = 56 AND sum2 = 52
sum1 = 57 AND sum2 = 51 .......so on
pseudo code
SUM=Array.sum();
sum1 = SUM/2;
sum2 = SUM-sum1;
while(true){
if(subSetSuMProblem(A,sum1) && subSetSuMProblem(A,sum2){
print "possible"
break;
}
else{
sum1++;
sum2--;
}
}
Java code for the same
import java.util.ArrayList;
import java.util.List;
public class MinimumSumSubsetPrint {
public static void main(String[] args) {
int[] A = {10, 20, 15, 5, 25, 32};
int sum = 0;
for (int i = 0; i < A.length; i++) {
sum += A[i];
}
subsetSumDynamic(A, sum);
}
private static boolean subsetSumDynamic(int[] A, int sum) {
int n = A.length;
boolean[][] T = new boolean[n + 1][sum + 1];
// sum2[0][0]=true;
for (int i = 0; i <= n; i++) {
T[i][0] = true;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (A[i - 1] > j) {
T[i][j] = T[i - 1][j];
} else {
T[i][j] = T[i - 1][j] || T[i - 1][j - A[i - 1]];
}
}
}
int sum1 = sum / 2;
int sum2 = sum - sum1;
while (true) {
if (T[n][sum1] && T[n][sum2]) {
printSubsets(T, sum1, n, A);
printSubsets(T, sum2, n, A);
break;
} else {
sum1 = sum1 - 1;
sum2 = sum - sum1;
System.out.println(sum1 + ":" + sum2);
}
}
return T[n][sum];
}
private static void printSubsets(boolean[][] T, int sum, int n, int[] A) {
List<Integer> sumvals = new ArrayList<Integer>();
int i = n;
int j = sum;
while (i > 0 && j > 0) {
if (T[i][j] == T[i - 1][j]) {
i--;
} else {
sumvals.add(A[i - 1]);
j = j - A[i - 1];
i--;
}
}
System.out.println();
for (int p : sumvals) {
System.out.print(p + " ");
}
System.out.println();
}
}
Here is recursive approach
def helper(arr,sumCal,sumTot,n):
if n==0:
return abs(abs(sumCal-sumTot)-sumCal)
return min(helper(arr,sumCal+arr[n-1],sumTot,n-1),helper(arr,sumCal,sumTot,n-1))
def minimum_subset_diff(arr,n):
sum=0
for i in range(n):
sum+=arr[i]
return helper(arr,0,sum,n)
Here is a Top down Dynamic approach to reduce the time complexity
dp=[[-1]*100 for i in range(100)]
def helper_dp(arr,sumCal,sumTot,n):
if n==0:
return abs(abs(sumCal-sumTot)-sumCal)
if dp[n][sumTot]!=-1:
return dp[n][sumTot]
return min(helper_dp(arr,sumCal+arr[n-1],sumTot,n-1),helper_dp(arr,sumCal,sumTot,n-1))
def minimum_subset_diff_dp(arr,n):
sum=0
for i in range(n):
sum+=arr[i]
return helper_dp(arr,0,sum,n)
int ModDiff(int a, int b)
{
if(a < b)return b - a;
return a-b;
}
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 O(n!) solution does compute the way we can divide the given array into 2 parts such the difference is minimum. But definitely not practical due to the n! time complexity looking to improve this using DP.
#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;
}
Many answers mentioned about getting an 'approximate' solution in a very acceptable time bound . But since it is asked in an interview , I dont expect they need an approximation algorithm. Also I dont expect they need a naive exponential algorithm either.
Coming to the problem , assuming the maximum value of sum of numbers is known , it can infact be solved in polynomial time using dynamic programming. Refer this link https://people.cs.clemson.edu/~bcdean/dp_practice/dp_4.swf
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***
