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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

Starter code: class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        

Solutions:
class Solution:

	def canPartition(self, nums):
		_sum = sum(nums)
		(div, mod) = divmod(_sum, 2)
		if mod != 0:
			return False
		target = [div] * 2
		self._len = len(nums)
		nums.sort(reverse=True)

		def dfs(index, target):
			if index == self._len:
				return True
			num = nums[index]
			for i in range(2):
				if target[i] >= num:
					target[i] -= num
					if dfs(index + 1, target):
						return True
					target[i] += num
			return False
		return dfs(0, target)


class Solution:

	def canPartition(self, nums):
		_sum = sum(nums)
		(div, mod) = divmod(_sum, 2)
		if mod or max(nums) > div:
			return False
		nums.sort(reverse=True)
		target = [div] * 2
		return self.dfs(nums, 0, target)

	def dfs(self, nums, index, target):
		for i in range(2):
			if target[i] >= nums[index]:
				target[i] -= nums[index]
				if target[i] == 0 or self.dfs(nums, index + 1, target):
					return True
				target[i] += nums[index]
		return False


class Solution:

	def canPartition(self, nums):
		nums.sort(reverse=True)
		print(nums)
		numsum = sum(nums)
		if numsum % 2 != 0:
			return False
		halfsum = numsum // 2
		t_sum = nums[0]
		if t_sum > halfsum:
			return False
		elif t_sum == halfsum:
			return True
		llen = len(nums)
		for startpos in range(1, llen):
			curpos = startpos
			while t_sum < halfsum and curpos < llen:
				if t_sum + nums[curpos] > halfsum:
					curpos += 1
				elif t_sum + nums[curpos] == halfsum:
					return True
				else:
					t_sum += nums[curpos]
					curpos += 1
				pass
			t_sum = nums[0]
		return False


class Solution:

	def search(self, nums, pos, target, seen):
		if (pos, target) in seen:
			return False
		if target == 0:
			return True
		if pos >= len(nums) or nums[pos] > target:
			return False
		if self.search(nums, pos + 1, target - nums[pos], seen):
			return True
		if self.search(nums, pos + 1, target, seen):
			return True
		seen.add((pos, target))
		return False

	def canPartition(self, nums):
		s = sum(nums)
		if s % 2 == 1:
			return False
		target = s // 2
		nums = sorted(nums)
		return self.search(nums, 0, target, set())


class Solution:

	def canPartition(self, nums):
		if len(nums) < 2:
			return False
		s = sum(nums)
		if s % 2 != 0:
			return False
		s = s // 2
		nums.sort()
		mem = dict()
		return self.dp(nums, 0, s, mem)

	def dp(self, nums, start, s, mem):
		if s == 0:
			return True
		if start >= len(nums):
			return False
		state = mem.get((start, s), None)
		if state is not None:
			return state
		res = False
		if nums[start] > s:
			res = False
		else:
			res = self.dp(nums, start + 1, s - nums[start], mem) or self.dp(nums, start + 1, s, mem)
		mem[start, s] = res
		return res


class Solution:

	def canPartition(self, nums):
		sum_ = sum(nums)
		if sum_ % 2 == 0:
			target = sum_ / 2

			def myFun(t, nu):
				nu.sort()
				nu.reverse()
				for (index, item) in enumerate(nu):
					if item == t:
						return True
					elif item > t:
						return False
					else:
						nun = nu.copy()
						del nun[index]
						if myFun(t - item, nun):
							return True
						elif index == len(nu) - 1:
							return False
			return myFun(target, nums)
		return False


class Solution:

	def canPartition(self, nums):
		s = 0
		bits = 1
		for num in nums:
			s += num
			bits |= bits << num
		return not s & 1 and bits >> (s >> 1) & 1 == 1


class Solution:

	def canPartition(self, nums):
		s = sum(nums)
		if s & 1:
			return False
		target = s // 2
		cnt = collections.Counter(nums)
		return self.helper(target, cnt)

	def helper(self, target, cnt):
		if target == 0:
			return True
		if target < 0:
			return False
		for item in sorted(list(cnt.keys()), reverse=True):
			if cnt[item] == 0:
				continue
			cnt[item] -= 1
			if self.helper(target - item, cnt):
				return True
			cnt[item] += 1
		return False


class Solution:

	def canPartition(self, nums):
		target = sum(nums)
		if target % 2 == 1:
			return False
		target = target // 2
		if any([x for x in nums if x > target]):
			return False
		nums.sort()

		def check(nums, target):
			if target in nums:
				return True
			if not nums or nums[0] > target:
				return False
			res = False
			tag = '@'
			for i in range(len(nums)):
				if tag != nums[i]:
					tag = nums[i]
					res = res | check(nums[:i] + nums[i + 1:], target - nums[i])
					if res:
						return True
			return res
		return check(nums, target)