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]; };