partition_equal_subset_sum
1from functools import cache 2 3 4# @leet start 5class Solution: 6 def canPartition(self, nums: list[int]) -> bool: 7 """ 8 This question asks if we can partition the list `nums` into two subsets 9 where the sums are equal. 10 11 To solve this, we note that the subset sum can only be split into two if 12 it is even (odd numbers are not divisible by 2), and instead of checking 13 for both the left and right subsets equaling each other, we can just check 14 if one side is equal to half the subset sum (by definition, that means 15 both are equal). 16 17 We then go through each index either choosing to add the number to our 18 sum or not. At any time, if our current equals the subset sum, we return 19 true, or if we hit the end of the array or curr > subset sum, we return 20 false. 21 """ 22 total_sum = sum(nums) 23 if total_sum % 2 != 0: 24 return False 25 26 subset_sum = total_sum // 2 27 28 n = len(nums) 29 30 @cache 31 def dfs(i, curr): 32 if curr == subset_sum: 33 return True 34 if curr > subset_sum or i == n: 35 return False 36 return dfs(i + 1, curr + nums[i]) or dfs(i + 1, curr) 37 38 return dfs(0, 0) 39 40 41# @leet end 42 43 44def test(): 45 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def canPartition(self, nums: list[int]) -> bool: 8 """ 9 This question asks if we can partition the list `nums` into two subsets 10 where the sums are equal. 11 12 To solve this, we note that the subset sum can only be split into two if 13 it is even (odd numbers are not divisible by 2), and instead of checking 14 for both the left and right subsets equaling each other, we can just check 15 if one side is equal to half the subset sum (by definition, that means 16 both are equal). 17 18 We then go through each index either choosing to add the number to our 19 sum or not. At any time, if our current equals the subset sum, we return 20 true, or if we hit the end of the array or curr > subset sum, we return 21 false. 22 """ 23 total_sum = sum(nums) 24 if total_sum % 2 != 0: 25 return False 26 27 subset_sum = total_sum // 2 28 29 n = len(nums) 30 31 @cache 32 def dfs(i, curr): 33 if curr == subset_sum: 34 return True 35 if curr > subset_sum or i == n: 36 return False 37 return dfs(i + 1, curr + nums[i]) or dfs(i + 1, curr) 38 39 return dfs(0, 0)
def
canPartition(self, nums: list[int]) -> bool:
7 def canPartition(self, nums: list[int]) -> bool: 8 """ 9 This question asks if we can partition the list `nums` into two subsets 10 where the sums are equal. 11 12 To solve this, we note that the subset sum can only be split into two if 13 it is even (odd numbers are not divisible by 2), and instead of checking 14 for both the left and right subsets equaling each other, we can just check 15 if one side is equal to half the subset sum (by definition, that means 16 both are equal). 17 18 We then go through each index either choosing to add the number to our 19 sum or not. At any time, if our current equals the subset sum, we return 20 true, or if we hit the end of the array or curr > subset sum, we return 21 false. 22 """ 23 total_sum = sum(nums) 24 if total_sum % 2 != 0: 25 return False 26 27 subset_sum = total_sum // 2 28 29 n = len(nums) 30 31 @cache 32 def dfs(i, curr): 33 if curr == subset_sum: 34 return True 35 if curr > subset_sum or i == n: 36 return False 37 return dfs(i + 1, curr + nums[i]) or dfs(i + 1, curr) 38 39 return dfs(0, 0)
This question asks if we can partition the list nums into two subsets
where the sums are equal.
To solve this, we note that the subset sum can only be split into two if it is even (odd numbers are not divisible by 2), and instead of checking for both the left and right subsets equaling each other, we can just check if one side is equal to half the subset sum (by definition, that means both are equal).
We then go through each index either choosing to add the number to our sum or not. At any time, if our current equals the subset sum, we return true, or if we hit the end of the array or curr > subset sum, we return false.
def
test():