LeetCode416. 分割等和子集

題目鏈接：416. 分割等和子集

題目描述：

給你一個?只包含正整數?的?非空?數組?nums?。請你判斷是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。

示例 1：

輸入：nums = [1,5,11,5]
輸出：true
解釋：數組可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

輸入：nums = [1,2,3,5]
輸出：false
解釋：數組不能分割成兩個元素和相等的子集。

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

算法分析：

定義dp數組及下標含義：

dp[i][j]表示0~i中每個元素任取，其總和不大于j的最大值（能夠在容量為j的背包里裝下的最大值）。

遞推公式：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])。

初始化：

子集的總和不會超過原數組總和的一半，所以dp代表值的那個維度長度取其一半即可。

vector<vector<int>>dp(nums.size(), vector<int>(sum + 1, 0));for(int i = nums[0]; i <= sum; i++) {dp[0][i] = nums[0];}

遍歷順序：

元素遍歷的for循環在外層，總和值的遍歷在內層。

代碼如下：

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;for(int i = 0; i < nums.size(); i++) {sum += nums[i];}if(sum % 2 != 0) return false;sum /= 2;vector<vector<int>>dp(nums.size(), vector<int>(sum + 1, 0));for(int i = nums[0]; i <= sum; i++) {dp[0][i] = nums[0];}for(int i = 1; i < nums.size(); i++) {for(int j = 0; j <= sum; j++) {if(j < nums[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);if(dp[i][j] == sum) return sum;}}return false;}
};

狀態壓縮，將二維數組轉化成一維數組（內從循環遍歷總和值要倒著遍歷）：

class Solution{public boolean canPartition(int[] nums) {int sum = 0;for(int i = 0; i < nums.length; i++) sum += nums[i];if(sum % 2 != 0) return false;sum /= 2;int[] dp = new int[sum + 1];for(int i = nums[0]; i <= sum; i++)dp[i] = nums[0];for(int i = 1; i < nums.length; i++) {for(int j = sum; j >= nums[i]; j--) {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}if(dp[sum] == sum) return true;}return false;}
}

總結

對于類似背包的問題，可以將其視為背包問題看待，找準背包容量和物品的對應對象。