simple solution without using dynamic programing

  • 1

    each number in the array can be picked or not picked to form the subset of array to have a target sum. Here we can scan through the array, and store the sums of the subsets that include or not include the current number. We can use a set to store the sums to avoid duplicates.

        def canPartition(self, nums):
            total = sum(nums)
            if total % 2 == 1: return False
            target = total / 2   #target sum 
            s = set([0])         #stores the sums of the subsets
            for n in nums:
                sums_with_n = []  #stores the sums of the subsets that contain n
                for i in s:
                    if i + n == target: return True
                    if i + n < target:
                        sums_with_n.append(i + n)
            return False

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.