LeetCode 416 除以相等和子集

给定一个仅包含正整数的非空数组。 是否可以将此数组拆分为两个子集，以便两个子集的元素之和相等。

注意：每个数组中的元素不会超过 100 个

数组的大小不会超过 200

示例 1：输入：[1， 5， 11， 5]。

输出：true

说明：数组可以拆分为 [1， 5， 5] 和 [11]。

示例 2：输入：[1， 2， 3， 5]。

输出：false

解释：一个数组不能分为两个元素和相等的子集。

DFS动态规划，阿里腾讯的字节抽象能力在工程和算法中都占有绝对重要的地位。 例如，我们可以将上述问题抽象为：

给定一个非空数组，并且是 sum，您能找到这样一个 sum 为 2 sum 的子序列吗？

我们做了两个数字，三个数字，四个数字，看到这种类似的问题会不会更舒服一些，思维会更开放一些。

当老司机看到转换后的问题时，他们会立即想到背包问题，这里会提供深度优先搜索跟背包两种解决方案。

我们来看一下问题的描述，sum 有两种情况，如果 sum % 2 === 1，那么一定没有解，因为 sum 2 是小数，数组是由整数组成的，子数组的总和不能是小数。 如果 sum % 2 === 0，我们需要找到一个总和为 2 的子序列 对于 2，我们需要在 nums 中找到满足条件的子序列。 这个过程可以类似于一个有n个球的大篮子，每个球代表一个不同的数字，我们用一个小篮子来抓球，这样球的总和就是2个总和。 那么一个自然的想法是，对于大篮筐里的每一个球，我们考虑是否拿下它，如果我们有足够的耐心，我们一定能够穷尽所有的情况，判断是否有解决方案。 上述思路以伪**形式表示如下：

设 target = sum 2， nums 为输入数组，cur 为当前要选择的数字的索引nums 为输入数组，target 为当前总和目标，cur 为当前判断函数 dfs（nums， target， cur） 如果目标 < 0 或 cur > numslength return false 否则，如果 target = 0，则找到答案，返回 true 否则，无论是否取当前数字，输入递归 dfs（nums， target - nums[cur]， cur + 1） |dfs(nums, target, cur + 1)

var canpartition = function (nums) sum = sum / 2; return dfs(nums, sum, 0);}function dfs(nums, target, cur) return ( target === 0 ||dfs(nums, target - nums[cur], cur + 1) |dfs(nums, target, cur + 1) )

如果 nums 中的最大值是 > 2 和，那么一定没有解 在搜索过程中，我们取或不取每个数字，数组中的所有项目都是正数。 我们将数字的总和设置为pickedsum，pickedsum <= 2 sum 并不难，并且需要丢弃的数量discardsum，选择总和<=2总和并不难。 我们引入了两个约束来增强修剪：

优化后的**如下。

var canpartition = function (nums) sum = sum / 2; nums = nums.sort((a, b) => b - a); if (sum < nums[0]) return dfs(nums, sum, sum, 0);}function dfs(nums, pickremain, discardremain, cur) if (pickremain < 0 ||discardremain < 0 ||cur > nums.length) return ( dfs(nums, pickremain - nums[cur], discardremain, cur + 1) |dfs(nums, pickremain, discardremain - nums[cur], cur + 1) )

在使用 DFS 时，我们并不关心获取的规则，只要我们确保要获取的号码之前没有被获取过即可。 如果我们有取数策略的有规律的排列，比如说，第一个数字排在第一位，第二个数字排在第二位，在判断第i位数字是数字时，我们已经知道第一个i-1数字是不是每次都是所有子序列的组合， 并将集合 s 记录为该子序列的总和。看取第i位的情况，有两种情况可以采取或不采取。

如果 target-nums[i] 在集合 s 中，则返回 true，表示可以找到第一个 i 数并且不取目标的序列，如果目标在集合 s 中，则返回 true，否则返回 false，即第一个 i 数能否构成目标之和的子序列取决于第一个 i-1 的数。

注意 f[i， target] 是 nums 数组中的前 i 个数字是否可以形成 和 是 target 的子序列的可能性，则状态转移方程是。

f[i, target] = f[i - 1, target] |f[i - 1, target - nums[i]]

状态转移方程出来了，**写得非常好，DFS+dp可以求解，有不清楚的可以参考递归和动态规划，这里只提供dp解伪**表示

n = nums.lengthtarget 是 nums 数的总和，如果目标不能被 2 整除，则返回 false，使 dp 为 n * 目标的二维矩阵，最初 false 遍历 0：n，dp[i][0] = true 表示前 i 个数字的总和是 0 到 n 遍历 0 到目标，如果当前值 j 大于 nums[i] dp[i + 1][j] = dp[i][j-nums[i]] dp[ i][j] else dp[i+1][日] = dp[i][日]

j**ascript 实现

var canpartition = function (nums) else const dp = array.from(nums).map(()=> array.from().fill(false) )for (let i = 0; i < nums.length; i++)for (let i = 0; i < dp.length - 1; i++)return dp[nums.length - 1][sum];}

假**。

遍历 0 到 n 遍历 j 如果当前值 j 大于 nums[i] dp[j] = dp[j-nums[i]] dp[j] 否则 dp[j] = dp[j].

var canpartition = function (nums) sum = sum / 2; const dp = array.from().fill(false); dp[0] = true; for (let i = 0; i < nums.length; i++)return dp[sum];}

背包问题的特点是我们可以选择放或不放每件物品。 设 f[i， v] 表示将前 i 件物品放入容量为 v 的背包中的状态。

对于上面描述的背包，f[i， v] 表示可以获得的最大值，则状态跃迁方程为。

f[i, v] = max

f[i, v] = f[i-1, v] |f[i-1, v-ci]

给定不同面额的硬币和总金额。 编写一个函数来计算可以组合成总金额的硬币组合数。 假设每种面额的硬币数量无限。

j**ascript 实现

/** param amount * param coins * return */var change = function (amount, coins) )fill(0); dp[0] = 1; for (let i = 0; i < coins.length; i++)return dp[amount];}

复杂性分析

时间复杂度：$o（金额 * len（coins））$Space复杂度：$o（amount）$