01 背包面试题系列（一）
题目形容——宰割等和子集
给你一个 只蕴含正整数 的 非空 数组
nums。请你判断是否能够将这个数组宰割成两个子集，使得两个子集的元素和相等。示例 1：
输出：nums = [1,5,11,5] 输入：true 解释：数组能够宰割成 [1, 5, 5] 和 [11]。示例 2：
输出：nums = [1,2,3,5] 输入：false 解释：数组不能宰割成两个元素和相等的子集。
01 背包动静布局求解
下面的问题乍一看如同是一个子集划分的问题，咱们可能依据数据 nums 失去它的所有的子集，而后将所有的本人加起来看看是否存在一个子集的数据的和等于 nums 数组所有数据的和的一半，其实咱们的确能够这样做，咱们将在后文当中认真探讨这个办法。
那么咱们改如何应用 01 背包 去解决这个问题呢？咱们首先先回顾一下 01 背包 解决了什么问题：
有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能应用
一次。第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
01 背包 就是给定肯定容量的背包，看他可能装入物品的最大的价值。那么咱们该如何将上述问题转化成 01 背包 呢？
咱们能够这样，将 nums 数组当中的数值变成物品对应的价值和体积，比如说 nums = [1, 2, 3]，咱们就能够分成三个物品，这三个物品的体积和价值别离是 1 和 1 、 2 和 2 和 3 和 3 ，咱们背包的容量为 V = (1 + 2 + 3) / 2。咱们将nums 数组当中所有数据和的一半作为背包的容量，nums当中的数值就示意每一个物品的价值和体积，而且价值和体积都相等，如果咱们可能恰好装满背包就阐明，存在一种物品的组合他的和为 nums 数组当中数据的和的一半。
那么咱们该如何判断背包被恰好装满呢？咱们晓得背包问题求解的只是在背包容量肯定的状况下，咱们可能获取的最大的价值是多少，因而如同不可能判断背包是否装满！然而在下面转化的过程当中物品的体积和价值是相等的，因为咱们能够依据咱们取得的最大价值判断，如果咱们最终失去的收益等于背包的容量，那么阐明背包被填满了，也就是存在一种物品的组合咱们可能获取的最大的价值等于数组当中数据和的一半。因为物品的价值和体积相等，因而把背包填满和获取最大价值是等价的。
因而依据下面的剖析，如果咱们想用 01 背包去解决这个问题，咱们能够将背包容量设置为 nums 数组当中数据和的一半，物品的个数为数组的长度，物品的价值和体积为数组当中对应地位的值，而后进行 01 背包求解即可。
如果你还不是很理解 01 背包的话，能够先看这篇文章，该文章次要从 0 开始介绍了 01 背包问题，从二维数组到滚动数组再到一维数组，优化过程层层递进，带你从原理到实战齐全把握 01 背包问题。
因而咱们的代码如下（一维数组优化）：
class Solution {public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {sum += num;}
if ((sum & 1) == 1) return false;
int t = sum / 2;
int[] dp = new int[t + 1];
for (int i = 0; i < nums.length; i++) {for (int j = t; j >= nums[i]; j--) {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return dp[t] == t;
}
}子集划分求解
咱们晓得任何一个汇合的子集个数为 $2^n$，其中 $n$ 示意汇合当中数据的个数，比如说汇合 ${1, 2}$ 有如下子集（4 个）：
$$
\{空集 \}, \{1\}, \{2\}, \{1, 2\}
$$
咱们先思考一下 $2^n$ 是怎么计算出来的！咱们在生成子集的时候对于每一个数据都有抉择和不抉择两种状况，这其实就变成了一个排列组合问题。在下面的例子当中 1 可选可不选（2），2 可选可不选（2），因而总的汇合个数为 4，那么如果有 n 个数据的汇合那么本人个数就等于：
$$
2\times2\times2 \cdots = 2^n
$$
这个抉择状况的划分如下图所示：
而咱们应用程序去计算一个汇合的子集其实就是一个回溯的问题，宰割等和子集的子集划分的代码如下：
public class Solution {
private int target;
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {sum += num;}
if ((sum & 1) == 1 ) return false;
// 咱们最终的指标就是找到一个本人的和等于这个数
target = sum / 2;
return backTrace(-1, 0, nums);
}
/**
* @param curIndex 示意以后遍历的数组的地位
* @param curSum 以后汇合所有数据的和
* @param nums 待遍历的数组
* @return
*/
public boolean backTrace(int curIndex, int curSum, int[] nums) {if (curSum == target) return true;
// 这里是剪枝操作 如果以后的和曾经大于目标值或者
// 遍历的下标超过数组的长度了就返回 false 示意
// 这个分支没有找到一个汇合，汇合当中的数据之和等于 target
else if (curSum > target || curIndex >= nums.length - 1) return false;
// 抉择某个数据
curSum += nums[curIndex + 1];
if (backTrace(curIndex + 1, curSum, nums))
return true;
// 不抉择某个数据 对应这回溯的操作
curSum -= nums[curIndex + 1];
return backTrace(curIndex + 1, curSum, nums);
}
}
咱们晓得动静布局的工夫复杂度为 $O(n^2)$，而这个应用生成子集的办法的话工夫复杂度为 $O(2^n)$。因而如果你再 LeetCode 上提交这个代码会超时。
总结
本文次要给大家介绍 宰割等和子集 这个题目，这个题目的即能够应用动静布局进行求解也能应用回溯法进行求解，然而回溯法求解问题的工夫复杂度太高。应用动静布局求解的办法还是比拟形象，可能须要大家花工夫好好推敲一下，心愿大家有所播种，我是 LeHung，咱们下期再见！！！（记得 点赞 珍藏哦！）
更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu…
关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。