# Dynamic Programming - Partition Equal Subset Sum

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

DP

## Problem

Given an integer array `nums`

, return `true`

*if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or* `false`

*otherwise*.

**Example 1:**

1
2
3

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

**Example 2:**

1
2
3

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

## Solution

Before we get started with any solution, the following is very clear. We need to use the elements in any order and find if they could make two groups each having sum equal to `target`

.

1
2
3
4

if sum(nums)%2==1:
return False
target = sum(nums)//2

### DFS Solution

Seems fairly straightforward from a DFS solution standpoint. We can use **template 2** that we have already discussed here.

The idea is not to find two sets of group, rather just find one path which leads to the target. Since we know the actual sum is double than the `target`

then the remaining numbers **must** be added to make the other `target`

value.

Now if we restructure the problem to this - “ Find if the elements of an array can make the target value when used only once”, it becomes much simpler to implement and we can use the same intuition when implementing using the dynamic programming approach.

Start with the terminating conditions, if the current `target==0`

then we know we have successfully reached to the end, so can return `True`

, conversely if the `target`

anytime is negative then we know we have overshoot the `target`

and current path can not reach to a valid `target`

, so we return `False`

.

1
2
3
4
5

def dfs(index, target):
if target == 0:
return True
if target < 0:
return False

Now if we still have a positive `target`

, we can loop and consider every other elements to find the target. If we ever find a `True`

immediately return it. In case there is no success, return `False`

at the end of the loop.

1
2
3
4
5

for j in range(index,len(nums)):
if dfs(j+1, target - nums[j]):
return True
return False

Finally call `dfs()`

and return its return.

1

return dfs(0,target)

Even though this is a valid code, it will take `O(2^n)`

time, hence won’t pass LeetCode, however we will use the similar concept below to implement using the dynamic programming.

### Dynamic Programming

As discussed earlier we will use the same intuition. We need to find a target sum by using the numbers only once from an array. One way we can do this in `O(n)`

time is for every element we find the sum for every combination. The space complexity will be large though.

Below is an example, we are going to iterate through the array from left to right and keep all the summations in a `set`

. Initially we start with a set having just a `0`

as base case. Then we add `1`

and keep both. Then we take `5`

, find the new summations and append them to the set as well (`0 + 5 = 5, 1 + 5 = 6`

). We can keep doing this till the end of the loop.

If we have `target`

in the `set`

then we know we can reach it using the numbers to we return `True`

. The best part is, we don’t even have to wait for the loop to complete, we can return `True`

as soon as there is a `target`

in the `set`

.

1
2
3
4
5
6
7
8
9
10

cache = set([0])
for i in range(len(nums)):
copy_of_cache=cache.copy()
for digit in copy_of_cache:
cache.add(nums[i]+digit)
# We do not have to wait for the loop to complete.
if target in cache:
return True
return False

## Final Code

Here is the full code.

### DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def can_partition(nums):
if sum(nums) % 2 == 1:
return False
target = sum(nums)//2
def dfs(index, target):
if target == 0:
return True
if target < 0:
return False
for j in range(index,len(nums)):
if dfs(j+1, target - nums[j]):
return True
return False
return dfs(0, target)

### Dynamic Programming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def can_partition(nums):
if sum(nums) % 2 == 1:
return False
target = sum(nums)//2
cache = set([0])
for i in range(len(nums)):
copy_of_cache = cache.copy()
for digit in copy_of_cache:
cache.add(nums[i]+digit)
# We do not have to wait for the loop to complete.
if target in cache:
return True
return False