Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/416.html
416. Partition Equal Subset Sum
Level
Medium
Description
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:
- Each of the array element will not exceed 100.
- The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
Solution
First calculate the sum of the numbers in the array nums
. If the sum is odd, then it is impossible to partition the array into two subsets that have equal sum, so return false
.
Let length
be the length of the array nums
and let target
be half of the sum of the numbers in the array nums
. Use dynamic programming. Create a 2D array dp
of type boolean
with length
rows and target + 1
columns, where dp[i][j]
represents whether it is possible to select some numbers from the first i
numbers of nums
such that they sum up to j
, where j
ranges from 0 to target
. Initialize column 0 for each row to be true
since selecting nothing will lead to sum 0. Then initialize dp[0][nums[0]] = true
. For i
from 1 to length - 1
, let num = nums[i]
, and for each j
from 1 to target
, update dp[i][j]
as dp[i - 1][j] || dp[i - 1][j - num]
, where the latter can only be applied when j >= num
. If the first i - 1
numbers contain one or more numbers that sum up to j
, then when the i
-th number is added, the same numbers still sum up to j
. If j >= num
and the first i - 1
numbers contain one or more numbers that sum up to j - num
, then when the i
-th number which is num
is added, the same numbers still sum up to j - num
, and the same numbers with the newly added number num
will sum up to j
.
Finally, return dp[length - 1][target]
.
-
import java.util.Arrays; public class Partition_Equal_Subset_Sum { public static void main(String[] args) { Partition_Equal_Subset_Sum out = new Partition_Equal_Subset_Sum(); Solution s = out.new Solution(); System.out.println(s.canPartition(new int[]{1, 5, 11, 5})); System.out.println(s.canPartition(new int[]{1, 2, 3, 5})); } class Solution { public boolean canPartition(int[] nums) { if (nums == null || nums.length == 0) { return false; } // in case overflow, should use long int sum = sum = Arrays.stream(nums).sum(); if (sum % 2 != 0) { // two equal subsets, then sum must be 2*x return false; } int target = sum / 2; // dp[i] 表示原数组是否可以取出若干个数字,其和为i boolean[] dp = new boolean[target + 1]; dp[0] = true; for (int i = 0; i < nums.length; i++) { for (int v = target; v >= nums[i]; v--) { dp[v] = dp[v] || dp[v - nums[i]]; } } return dp[target]; } } class Solution_Bitset { /* bool canPartition(vector<int>& nums) { bitset<5001> bits(1); int sum = accumulate(nums.begin(), nums.end(), 0); for (int num : nums) bits |= bits << num; return (sum % 2 == 0) && bits[sum >> 1]; } */ } // only when subset has 2 elements class Solution_2sum { public boolean canPartition(int[] nums) { if (nums == null || nums.length == 0) { return false; } // in case overflow long sum = Arrays.stream(nums).reduce(0, (x, y) -> (x + y)); if (sum % 2 == 1) { return false; // two equal subsets, then sum must be 2*x } // then it's 2Sum question to sum/2 Two_Sum twoSum = new Two_Sum(); Two_Sum.Solution twoSumSolution = twoSum.new Solution(); Arrays.sort(nums); // possible overflow return twoSumSolution.twoSum(nums, (int)sum/2) == null; } } } ############ class Solution { public boolean canPartition(int[] nums) { int s = 0; for (int v : nums) { s += v; } if (s % 2 != 0) { return false; } int n = s >> 1; boolean[] dp = new boolean[n + 1]; dp[0] = true; for (int v : nums) { for (int j = n; j >= v; --j) { dp[j] = dp[j] || dp[j - v]; } } return dp[n]; } }
-
// OJ: https://leetcode.com/problems/partition-equal-subset-sum/ // Time: O(2^N) // Space: O(2^N) class Solution { public: bool canPartition(vector<int>& A) { int total = accumulate(begin(A), end(A), 0); if (total % 2) return false; unordered_set<int> s, next; for (int n : A) { next = s; for (int m : s) next.insert(m + n); next.insert(n); if (next.count(total / 2)) return true; swap(s, next); } return false; } };
-
class Solution: def canPartition(self, nums: List[int]) -> bool: s = sum(nums) if s % 2 != 0: return False n = s >> 1 dp = [False] * (n + 1) dp[0] = True for v in nums: for j in range(n, v - 1, -1): # including v itself dp[j] = dp[j] or dp[j - v] return dp[-1] ############ class Solution(object): def canPartition(self, nums): """ :type nums: List[int] :rtype: bool """ s = sum(nums) if s == 0: return True if s % 2 == 0: s, current = s / 2, 0 for num in nums: current |= ((current or 1) << num) % (1 << (s + 1)) if current >= 1 << s: return True return False
-
func canPartition(nums []int) bool { s := 0 for _, v := range nums { s += v } if s%2 != 0 { return false } n := s >> 1 dp := make([]bool, n+1) dp[0] = true for _, v := range nums { for j := n; j >= v; j-- { dp[j] = dp[j] || dp[j-v] } } return dp[n] }
-
/** * @param {number[]} nums * @return {boolean} */ var canPartition = function (nums) { let s = 0; for (let v of nums) { s += v; } if (s % 2 != 0) { return false; } const m = nums.length; const n = s >> 1; const dp = new Array(n + 1).fill(false); dp[0] = true; for (let i = 1; i <= m; ++i) { for (let j = n; j >= nums[i - 1]; --j) { dp[j] = dp[j] || dp[j - nums[i - 1]]; } } return dp[n]; };