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）$