解题思路

本质上是一个01背包问题，特殊之处在于物品的价值和重量的同一个数字
可以参考力扣-416-分隔等和子集
然后这里的代码是做了空间优化的，原本的写法是二维dp
关键的状态转移方程可以这么理解：
遍历每个物品，如果背包容量j大于物品容量，那么有放和不放两种选择
不放，就等于放i-1个物品的最大价值
放了，就等于当前物品的价值+剩余容量可放的最大价值

返回值

最后的返回值可以做一个简单的变换，题目要求其实是要分两堆总和尽可能接近的数组（注意并不是切两半，而是随便抽数组元素）
也就是说，要min(sum1-sum2)==min((sum1+sum2)-2sum2)==min(sum-2sum2)
总和sum是个定值，那么就要sum2尽可能地大，尽可能地接近sum/2
sum2可以认为是总和较小、最接近sum/2的那一组，当sum2==sum/2，获得最好的结果，两堆相等

#include<iostream>
#include<vector>
#include<numeric>
using namespace std;

int main(){

    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i =0;i<n;i++) cin>>nums[i];

    int sum = accumulate(nums.begin(),nums.end(),0);
    int half = sum/2;

    vector<int> dp(half+1);

    for(int i = 1;i<=n;i++)
        for(int j = half;j>=nums[i-1];j--)
            dp[j]=max(dp[j],dp[j-nums[i-1]]+nums[i-1]);

    cout<< sum-2*dp[half];
    return 0;
 }

#include <iostream>
(720)#include <numeric>
using namespace std;
 
int main(void){
    int n;
    cin>>n;
    long num[n];
    for(int i=0;i<n;i++)cin >> num[i];
     
    long sum = accumulate(num,num+n,0);
    long half = sum/2;
     
    long dp[half+1] = {0};
     
    for(int i=0;i<n;i++)
        for(long j=half;j>=num[i];j--)
            dp[j] = max(dp[j],dp[j-num[i]]+num[i]);
     
    cout << sum - 2*dp[half] << endl;
     
    return 0;
}

转换为0-1背包问题，查看详细题解请移步至 A 或 B 或 C。

得到所有的取值，然后从sum/2的地方倒序找的第一个就是了

时间复杂度

from re import search
import sys


def minMinus(a: list):
    s = sum(a)
    search_range = s // 2 + 1
    dp = [False] * (search_range + 1)
    dp[0] = True
    for n in a:
        for j in range(search_range, n - 1, -1):
            if dp[j - n]:
                dp[j] = True
    for j in range(s // 2, -1, -1):
        if dp[j]:
            return abs(j - (s - j))
    return -1


N = int(input())
a = list(map(int, input().split()))
print(minMinus(a))

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        int[] stones = new int[n];
        for(int i = 0;i < n;i++){
            stones[i] = sc.nextInt();
        }
        int ans = helper(stones);
        System.out.println(ans);

    }

    public static int helper(int[] stones){
        int len = stones.length;
        /*
         1.换一种想法，就是将这些数字分成两拨，使得他们的和的差最小
         2.因此可以简单地把所有石头看作两堆,假设总重量为 sum,
         则问题转化为背包问题：如何使两堆石头总重量接近 sum / 2
         3.两堆石头的价值(重量)都只能接近
         */
        int totalStone = 0;
        for (int i : stones) {
            totalStone += i;
        }

        int maxCapacity = totalStone / 2;
        /*
         1.这个是0-1背包的dp定义，dp[i][w]:  前i个商品，当容量为w时，最大价值为dp[i][w]
         2.对照一下此题dp数组定义，dp[i][j]: 前i个石头，当容量为j时，最大重量为dp[i][j]
        */
        int[][] dp = new int[len + 1][maxCapacity + 1];
        for(int i = 1;i < len + 1;i++){
            for(int j = 1;j < maxCapacity + 1;j++){
                if(j < stones[i - 1]){
                    dp[i][j] = dp[i - 1][j];
                }else{              
                    dp[i][j] = Math.max(dp[i - 1][j]
                                ,dp[i - 1][j - stones[i - 1]] + stones[i - 1]);               
                }

            }                                 
        }

        return totalStone - 2*dp[len][maxCapacity];
    }
}

又是0-1背包问题

集合划分问题 Golang 动态规划 01背包

最长等差数列问题 Golang 暴力法
字母组合 Golang
验证IP地址 Golang

01背包问题，用一个set记录可能凑出来的值。超过所有数字之和的一半可以不用记录，因为必定有一个小于一半的互补的情况，可以得出一组最接近总和一半的值，总和得较大的另一组的和，大的一组减小的一组得。
用数组可能太占空间了，所以用一个set来记录，但golang没有内置的set，就用map凑合一下。

package main

import "fmt"

func main(){
    var n,sum,tmp int
    var nums []int
    vals:=make( map[int]bool)
    vals[0]=true
    fmt.Scan(&n)
    for i:=0;i<n;i++ {
        fmt.Scan(&tmp)
        nums=append(nums, tmp)
        sum+=tmp
    }
    for _,v:=range nums{
        toPush:=[]int{}
        for n,_:=range vals{
            if n+v<=sum/2{
                toPush=append(toPush, n+v)
            }
        }
        for _,v:=range toPush{
            vals[v]=true
        }
    }
    max:=0
    for i,_:=range vals{
        if i>max{
            max=i
        }
    }
    fmt.Println(sum-2*max)
}

import java.util.Scanner;
 
/**
 * @author Tang Haolin
 */
public class Main {
 
    private static long minDiff = Integer.MAX_VALUE;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
 
        long sum = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
            sum += nums[i];
        }
 
        long diff = sum;
 
        solve(nums, 0, diff);
 
        System.out.println(minDiff);
 
    }
 
    private static void solve(int[] nums, int l, long diff) {
        if (l == nums.length - 1) {
            long minAbsDiff = Math.min(diff, Math.abs(diff - 2 * nums[l]));
            minDiff = Math.min(minDiff, minAbsDiff);
            return;
        }
 
        solve(nums, l + 1, diff);
        solve(nums, l + 1, Math.abs(diff - 2 * nums[l]));
 
    }
 
初始化所有数字在一个集合A中，另外一个集合B为空，从A中拿取一个数到B，相当于在原本两个集合的差的基础上减去这个数的两倍，再求绝对值。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] arr = new int[n];
            int sum = 0;
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
                sum += arr[i];
            }
            int p = sum / 2;
            boolean[] f = new boolean[p + 1];
            f[0] = true;
            for (int i = 0; i < n; i++) {
                for (int j = p; j >= arr[i]; j--) {
                    f[j] = f[j - arr[i]];
                }
            }
            for (int i = p; i >= 0; i--) {
                if (f[i]) {
                    System.out.println(sum - i * 2);
                    break;
                }
            }
        }
    }
}

#include <bits/stdc++.h>
using namespace std;
int nums,sum;
//数组量要调整着足够大
int scores[100000],dp[100000];


//limit代表上线。上线就是数组总和的一半
int limit;

/**
 * 总体使用背包。对于一个数，可以选也可以不选。
 * 这样问题等价于选择一组数最接近于整个数组的一半
 * 原则是不能超过 数组总体的一般，也就是用limit限制住。

 * @return
 */
int main(){
    //输入到数组scores内
    cin >>nums;
    for (int i = 1; i <= nums; ++i) {
        cin >> scores[i];
        sum += scores[i];
    }
    //limit赋值
    limit = sum/2;

    //背包，在limit的状态下，可以选，也可以不选
    for (int i = 1; i <= nums; ++i) {
        for (int score = limit; score >= scores[i] ; --score) {
            dp[score] = max(dp[score],dp[score-scores[i]]+scores[i]);
        }
    }

    //返回这里需要用返回两个的数组的差值
    cout << abs(sum - 2*dp[limit]);
    return 0;
}

import java.util.*;
public class Main{

    static int[][] matrix;

    static int[] cost;
    static int expense=0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        int[] target=new int[n];
        for (int i = 0; i <n; i++) {
            target[i]=scanner.nextInt();
        }
        Arrays.sort(target);
        int sum1=0;
        int sum2=0;
        for (int i = n-1; i >=0; i--) {
            if (sum1<sum2){
                sum1+=target[i];
            }else{
                // sum2 <= sum1
                sum2+=target[i];
            }
        }
        System.out.println(Math.abs(sum2-sum1));
    }
}

代码错了