416.Partition Equal Subset Sum

Tags: [knapsack], [01_knapsack]

Link: https://leetcode.com/problems/partition-equal-subset-sum/?tab=Description

Given anon-emptyarray containingonly 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: 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: knapsack, 01_knapsack

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if not nums or len(nums) <= 1 or sum(nums) % 2 != 0:
            return False

        half_sum = sum(nums) / 2
        max_num_of_elems_in_set1 = [[-sys.maxint - 1 for _ in xrange(half_sum + 1)] for _ in xrange(len(nums) + 1)]
        max_num_of_elems_in_set1[0][0] = 0

        for i in xrange(1, len(nums) + 1):
            num = nums[i - 1]
            for s in xrange(1, half_sum + 1):
                if num <= s:
                    max_num_of_elems_in_set1[i][s] = max(max_num_of_elems_in_set1[i - 1][s],
                                                         max_num_of_elems_in_set1[i - 1][s - num] + 1)
                else:
                    max_num_of_elems_in_set1[i][s] = max_num_of_elems_in_set1[i - 1][s]

        return 0 < max_num_of_elems_in_set1[len(nums)][half_sum] < len(nums)

Revelation:

• Because we can know the total sum of the nums, and it requires the sum of two subsets should be equal, so we can know the half_sum. We can think we have a bag, the volume of the bag is equal to half_sum. Now we try to use the nums to fill the bag, and we require that we should fully fill the bag, once we can get the max number of nums we need to use to fully fill the bag, we can check whether the number of nums we use to fill the bag is between 0 and the total number of nums.
• f[i][s] = max(f[i - 1][s], f[i - 1][s - nums[i]] + 1), f[i][s] means the max number of nums (chosen from first i nums) we need to use to fully fill the bag whose volume is s.

Note:

• Do not forget check the '0 < max num of elems in set1[len(nums)][halfsum]', because if the max num of elems in set1 can be min int, which means there is no way to fully fill the bag.
• Time complexity = O(n * sum), n is the number of the elements in the given array, sum is the sum of all numbers in the given array.

Time Limited Exceeded

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if not nums or len(nums) <= 1:
            return False

        return self.can_partition_helper(nums, 0, 0, sum(nums))

    def can_partition_helper(self, nums, index, sum1, sum2):
        # base case
        if sum1 == sum2:
            return True
        if index >= len(nums):
            return False


        return self.can_partition_helper(nums, index + 1, sum1 + nums[index], sum2 - nums[index]) or\
               self.can_partition_helper(nums, index + 1, sum1, sum2)

Revelation:

• Brute-force: try all possible way to choose the numbers to build the subset1.
• For each number, there are two choices, one is putting it to subset1, the other is putting it to subset2.

Note:

• Time complexity = O(2^n), n is the number of elements in the given array.