題目要求

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.Note: 1.Each of the array element will not exceed 100. 2.The array size will not exceed 200. Example 1:Input: [1, 5, 11, 5]Output: trueExplanation: The array can be partitioned as [1, 5, 5] and [11]. Example 2:Input: [1, 2, 3, 5]Output: falseExplanation: The array cannot be partitioned into equal sum subsets.

假設(shè)有一個全為正整數(shù)的非空數(shù)組，將其中的數(shù)字分為兩部分，確保兩部分?jǐn)?shù)字的和相等。

思路和代碼

這和0-1背包問題是完全一樣的，01背包問題是指假設(shè)有n個物品，每個物品中為weight[i]，假設(shè)背包的承重為k，問如何選擇物品使得背包中的承重最大。而這里的問題等價于，有n個物品，每個物品承重為input[i]，問如何挑選物品，使得背包的承重搞好為所有物品重量和的一般。

假設(shè)我們已經(jīng)知道前i個物品是否能夠構(gòu)成重量k，我們令該值為dpi，那么第i+1個物品是否能夠構(gòu)成重量取決于dpi和dpi], 即i+1個物品能夠構(gòu)成重量k有兩種情況，第一種選擇了i+1個物品，則要尋找前i個物品是否構(gòu)成k-input[i+1]的重量，第二種就是沒有選擇第i+1個物品，則直接判斷前i個物品是否已經(jīng)構(gòu)成了k的重量。

代碼如下：

public boolean canParition(int[] nums) {int sum = 0;for(int n : nums) {sum += n;}if(sum % 2 != 0) return false;int half = sum / 2;boolean[][] sums = new boolean[nums.length+1][half+1];for(int i = 0 ; i<=nums.length ; i++) {for(int j = 0 ; j<=half ; j++) {if(i==0 && j==0){sums[i][j] = true;}else if(i==0) {sums[i][j] = false;}else if(j==0){sums[i][j] = true;}else {sums[i][j] = sums[i-1][j] || (nums[i-1] <= j ? sums[i-1][j-nums[i-1]] : false);}}}return sums[nums.length][half];}

總結(jié)

以上是生活随笔為你收集整理的leetcode416. Partition Equal Subset Sum的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。