题意

给定数组$presentVecpresentVec$presentVec，把数组拆分成两个子数组，使得两个子数组分别的和的差最小。

范围，数组长度$n\le 100n\; \backslash leq\; 100$n≤100, 所有值$11$1到$100100$100之间

方法

深搜(TLE)

代码

我们可以枚举所有的选择方案，选或者不选。

那么有$dfs\left(当前选择位置，当前选择总和\right)dfs(当前选择位置，当前选择总和)$dfs(当前选择位置，当前选择总和)

递归的方案分为选和不选

不选的话，那么总和不变$dfs(当前选择位置+1，当前选择总和)dfs(当前选择位置+1，当前选择总和)$dfs(当前选择位置+1，当前选择总和)

选择的话，总和加上当前位置的值$dfs(当前选择位置+1，当前选择总和+数组[当前选择位置\left]\right)dfs(当前选择位置+1，当前选择总和+数组[当前选择位置])$dfs(当前选择位置+1，当前选择总和+数组[当前选择位置])

然后在递归的末端计算差值，在每一层比较并返回最小值。最顶层可得到答案。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param presentVec int整型一维数组 每个礼物的价值
# @return int整型
#
class Solution:
    def dfs(self , presentVec,s,idx, cnt):
        if idx == len(presentVec):
            return abs(s - 2*cnt)
        return min(
            self.dfs(presentVec, s, idx+1, cnt),
            self.dfs(presentVec, s, idx+1, cnt + presentVec[idx])
        )
        
        
    def maxPresent(self , presentVec ):
        return self.dfs(presentVec,sum(presentVec),0,0)

复杂度分析

时间复杂度: 我们对每一位遍历了是否取用，所以时间复杂度为$O\left(2^n\right)O(2^n)$O(2n)

空间复杂度: 通过dfs，其栈的使用与递归深度有关，所以时间复杂度为$O\left(n\right)O(n)$O(n)

动态规划

要两个人的差最小，而已经知道两个人的和=所有数字的总和。

那么只要知道其中一个人的值，就能知道另一个人的值。

那么我们如果能求出其中一个人所有可能获得的值，再在这些值中看哪个会让差值最小，题目就解决了。

那么问题变成了如何计算所有可能值呢。

以示例1为例, 可选的是$[1,2,3,4][1,2,3,4]$[1,2,3,4]，总和为$1010$10

最开始，因为没有选择任何的。 我们的可行状态为

接下来如果不选择$11$1，那么还是仅有$00$0是可达到的总和。

如果选了$11$1，那么$0+1=10+1=1$0+1=1也是可达的值

接下来是$22$2, 不选择的话，那么就是上面$00$0和$11$1可达。

如果要选择，则是$0+2=20+2=2$0+2=2和$1+2=31+2=3$1+2=3

接下来是$33$3

一样的道理，原来可达的依然可达，新增的可达都是由原来的可达加上$33$3

所以$0+3=30+3=3$0+3=3可达,$1+3=41+3=4$1+3=4可达,$2+3=52+3=5$2+3=5可达,$3+3=63+3=6$3+3=6可达,

最后是$44$4，新增的可达对应的是$44$4到$1010$10

说明了所有都可达。

最后来找最小的差$=min\left(\mid \right(sum-v)-v)\mid )=min(\mid sum-2\cdot v\mid )=min(|(sum-v)-v)|)\; =\; min(|sum-2\backslash cdot\; v|)$=min(∣(sum−v)−v)∣)=min(∣sum−2⋅v∣), 在$v=5v=5$v=5 时取最小值

同理 题目的样例2: 数据为$[1,3,5][1,3,5]$[1,3,5], 和为$99$9, 可达变化表依次为

$min(\mid sum-2\cdot v\mid )min(|sum-2\backslash cdot\; v|)$min(∣sum−2⋅v∣) 在$v=4v=4$v=4和$v=5v=5$v=5 时取最小值

由此我们可以编写代码.

1. 初始化可达表
2. 遍历所有值，每次根据值更新表
3. 所有遍历完后，找表中能让差最小又可达的值即可

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param presentVec int整型vector 每个礼物的价值
     * @return int整型
     */
    int maxPresent(vector<int>& presentVec) {
        vector<bool> cost(10001,false);
        int s = 0;
        cost[0] = 1;
        for(auto v:presentVec){
            s+=v;
            // 倒序
            for(int newv=10000;newv>=v;newv--){
                cost[newv] = cost[newv] || cost[newv-v];
            }
        }
        int ans = 10000;
        for(int v=0;v<=10000;v++){
            if(!cost[v])continue;
            ans = min(ans,abs(s-2*v));
        }
        return ans;
    }
};

复杂度分析

空间复杂度: 我们仅用了是否可达的数组来记录状态，其余是都遍历的常数个临时变量，所以空间复杂度为$O\left(max\right(\sum presentVe{c}_i\left)\right)O(max(\backslash sum\{presentVec\_i\}))$O(max(∑presentVeci​))

时间复杂度: 我们对每一个值，推导其选入导致的数组变化，枚举了从总和到0之间的所有可行值。剩余部分求最接近的值耗费了$O\left(max\right(\sum presentVe{c}_i\left)\right)O(max(\backslash sum\{presentVec\_i\}))$O(max(∑presentVeci​))，所以空间复杂度为$O\left(max\right(\sum presentVe{c}_i)\cdot n)O(max(\backslash sum\{presentVec\_i\})\; \backslash cdot\; n)$O(max(∑presentVeci​)⋅n)