Check If There Is A Valid Partition For The Array - Leetcode Solution

Problem Statement:

Given an array of integers nums, divide the array into two non-empty subsets such that the sum of the elements in both subsets is equal. You can assume that you can always make this division. Return true if the array can be divided, otherwise, return false.

Example:

Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].

Solution: The problem can be solved using backtracking. We can start by calculating the total sum of the array. If the sum is odd, we cannot divide the array into two subsets with equal sum.

If the sum is even, we can start with an empty set and try to add elements to form a subset whose sum is half the total sum. If such a subset is found, it implies that the remaining elements also form a subset whose sum is half the total sum.

To find the subset whose sum is half the total sum, we can use backtracking. We can start by selecting the first element of the array and adding it to the current subset. Then we can select the next element and recursively check if we can form a subset whose sum is half the total sum with the remaining elements.

If we are not able to form a subset with the first element, we can backtrack and remove it from the current subset and try again with the next element. We can continue this until we find a subset whose sum is half the total sum, or we exhaust all the elements.

Python Code:

class Solution: def canPartition(self, nums: List[int]) -> bool: # calculate the total sum of the array total_sum = sum(nums)

    # if the sum is odd, we cannot form two subsets with equal sum
    if total_sum % 2 != 0:
        return False
    
    # sort the array in reverse order
    nums.sort(reverse=True)
    
    # call the helper function to find the subset with sum equal to half the total sum
    return self.helper(nums, 0, 0, total_sum // 2)

def helper(self, nums, index, current_sum, target):
    # base case
    if current_sum == target:
        return True
    
    # edge case
    if current_sum > target or index >= len(nums):
        return False
    
    # select the current element and check if we can form a subset with sum equal to half the total sum
    if self.helper(nums, index + 1, current_sum + nums[index], target):
        return True
    
    # do not select the current element and check if we can form a subset with sum equal to half the total sum
    if self.helper(nums, index + 1, current_sum, target):
        return True
    
    # if we cannot form a subset with the current element, backtrack and try with the next element
    return False

1