如何将一个集合分为两个子集，使得两个集合中的数字之和之间的差异最小？

Question

给定一组数字，将这些数字分为两个子集，使两个子集中的数字之和之间的差异最小。

这是我的想法，但我不确定这是否是正确的解决方案：

1. 对数组进行排序
2. 取前 2 个元素。将它们视为 2 个集合（每个集合有 1 个元素）
3. 从数组中取出下一个元素。
4. 决定该元素应该进入哪个集合（通过计算总和 => 它应该是最小值）
5. 重复

这是正确的解决方案吗？我们可以做得更好吗？

Answer 1

您所描述问题的决策版本是NP-complete 问题，称为 分区问题。有许多近似值，在许多情况下提供了最佳的或至少足够好的解决方案。

您描述的简单算法是游乐场孩子们选择团队的一种方式。如果集合中的数字具有相似的数量级，则此贪婪算法表现得非常好。

文章 最简单最难的问题，作者是美国科学家，对该问题进行了精彩的分析。你应该仔细阅读它！

Answer 2

不，那不行。不存在多项式时间解（除非 P=NP）。您能做的最好的事情就是查看所有不同的子集。看一下子集和问题。

考虑列表[0, 1, 5, 6]。您将声明 {0, 5} 和 {1, 6}，而最佳答案实际上是 {0, 1, 5} 并且<代码>{6}。

Answer 3

不，你的算法是错误的。你的算法遵循贪婪的方法。
我实现了你的方法，但在这个测试用例中失败了：
（您可以尝试此处）

贪心算法：

#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;
}

测试用例：

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

贪心算法失败的原因是它没有考虑当前较大和集中取较大元素而稍后在较大和集中取较小元素可能会产生更好结果的情况。它总是尝试最小化当前差异，而不探索或了解进一步的可能性，而在正确的解决方案中，您可能会在更大的集合中包含一个元素，并稍后包含一个更小的元素来补偿这种差异，与上面的测试用例相同。

正确的解决方案：

要理解该解决方案，您需要按顺序理解以下所有问题：

• 0/1 背包动态规划
• 分区相等带 DP 的子集和
• 解决方案

我的代码（与这个）：

#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 4

组合之上的组合方法：

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"

Answer 5

递归方法是从数组的所有值生成所有可能的和并检查
哪种解决方案是最优的。
为了生成总和，我们要么将第 i 个项目包含在集合 1 中，要么不包含，即包含在
集合2。

时间和空间的时间复杂度都是O(n*sum)。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 6

我们可以使用动态规划（类似于我们发现一个集合是否可以划分为两个等和子集的方法）。然后我们找到最大可能的总和，这将是我们的第一个分区。
第二个分区将是总和与第一个总和的差。
答案将是第一分区和第二分区的差异。

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);
}

Answer 7

也许你正在谈论这个。

<一href="https://practice.geeksforgeeks.org/problems/partition-a-set-into-two-subsets-such-that-the-difference-of-subset-sums- is-minimum-set-2/1?page=3&difficulty%5B%5D=2&status%5B%5D=unsolved&status%5B%5D=attempted&sortBy=difficulty" rel="nofollow noreferrer">https://practice.geeksforgeeks.org/problems/partition-a-set-into-two-subsets-such-that-the-difference-of-subse t-sums-is-minimum-set-2/1？page=3&difficulty[]=2&status[]=unsolved&status[]=attempted&sortBy=difficulty

我使用“中间相遇”的方法来做到这一点。它是一种优化技术，其工作原理是将数组分成两部分，然后生成子集。

代码，如有疑问请随时询问

    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

Answer 8

一个小改变：颠倒顺序——从最大的数字开始，然后依次递减。这将最大限度地减少错误。

Answer 9

您是否将子集按降序或升序排序？

想想看，数组 {1, 3, 5, 8, 9, 25}

如果你要除法，你会得到 {1,8,9} =18 {3,5,25} =33

如果它按降序排序，效果会更好

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

所以你的解决方案基本上是正确的，它只需要确保首先取最大值即可。

编辑：阅读 tskuzzy 的帖子。我的不工作

Answer 10

这是背包和子集和问题的变体。
在子集和问题中，给定n个正整数和一个值k，我们必须找到值小于或等于k的子集的和。
在上面的问题中，我们给定了一个数组，这里我们必须找到总和小于或等于total_sum(数组值的总和)的子集。
所以
可以使用背包算法的变体找到子集和，通过
将利润作为给定的数组值。最终的答案是
总和-dp[n][总和/2]。看一下下面的代码就清楚了
理解。

#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 11

这可以使用 BST 来解决。
首先对数组进行排序，比如 arr1
要开始使用 arr1 的最后一个元素创建另一个 arr2 （从 arr1 中删除该元素）

现在：重复这些步骤，直到没有交换发生。

1. 检查 arr1 是否有可以使用 BST 移动到 arr2 的元素，这样差异就小于到目前为止找到的 MIN diff。
2. 如果我们找到一个元素，则将该元素移动到 arr2 并再次转到步骤 1。
3. 如果我们在上述步骤中没有找到任何元素，请执行步骤 1 & 2 对于 arr2 和到达1。
   即现在检查 arr2 中是否有任何元素可以移动到 arr1
4. 继续步骤 1-4 直到我们不需要任何交换..
5. 我们得到了解决方案。

Java 代码示例：

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 12

您可以使用位来解决此问题，方法是使用位循环遍历所有可能的组合：
主要算法：

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);
}

使用 long long 以获得更大的输入。

但在这里我找到了一个递归和动态编程解决方案，我使用这两种方法来解决问题，并且都可以完美地获得更大的输入。希望这有帮助:) 解决方案链接

Answer 13

请检查我为这个问题编写的逻辑。它适用于我检查过的几个场景。请评论解决方案，
方法：

1. 对主数组进行排序，并将其分为 2 组。
2. 然后，根据代码中提到的条件，开始通过移位并将元素从一个数组交换到另一个数组，使团队相等。

如果差异是总和的差值小于较大数组（总和较大的数组）的最小数量，则将元素从较大数组移动到较小数组。移动发生的条件是，较大数组中的元素的值小于或等于差值。当较大数组中的所有元素都大于差值时，移位停止并发生交换。我只是交换数组的最后一个元素（通过查找要交换的两个元素可以提高效率），但这仍然有效。如果这个逻辑在任何情况下失败，请告诉我。

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 14

这里有一个可能的解决方案 - https://stackoverflow.com/a/31228461/4955513
这个 Java 程序似乎可以解决这个问题，只要满足一个条件——该问题只有一个解决方案。

Answer 15

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代码

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();
}


}

Answer 16

这是递归方法

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)

这是一种自上而下的动态方法来降低时间复杂度

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)

Answer 17

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;

}

使用 SumI =0 和 SumE= a 中所有元素的总和来调用该函数。
这个 O(n!) 解决方案确实计算了我们将给定数组分为两部分的方式，以使差异最小。
但由于 n! 绝对不实用。希望使用 DP 来改善时间复杂度。

Answer 18

#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 19

许多答案提到在非常可接受的时间内获得“近似”解决方案。但既然是在面试中被问到的，我不认为他们需要近似算法。我也不认为他们需要一个朴素的指数算法。

谈到这个问题，假设数和的最大值已知，实际上可以使用动态规划在多项式时间内求解。参考这个链接
https://people.cs.clemson.edu/~bcdean/dp_practice/dp_4 .swf

Answer 20

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***