## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Subset Sum Problem

Problem Statement

Given an set of non-negative integers, and a value `sum`, print out all the subsets of the given `array` whose elements have sum equal to given sum.

Solution

To solve the problem we use the Dynamic programming.

For the first step we will create a 2D array, `dp`, of size `[len(array)+1] * [sum + 1]` of type boolean. The state `dp[i][j]` will be true if there exists a subset of elements from `array[0….i]` with sum value = `j`.

The approach for the problem is:``` ```

```if (array[i] > j)
dp[i][j] = dp[i-1][j] // Don't include array[i] in the sum
else
dp[i][j] = dp[i-1][j] OR dp[i-1][j-array[i]] // Include array[i] in the sum```

Filling the dp Table

```def fill_dp(arr, s):
n = len(arr)

# The state dp[i][j] will be True if there exists a subset of elements from arr[0…i)
# with sum value = ‘j’.
dp = ([[False for j in range(s + 1)] for i in range(n + 1)])

# If sum is 0, then answer is true
for i in range(n+1):
dp[i][0] = True

# If sum is not 0 and set is empty, then answer is false
for j in range(1, s+1):
dp[0][j] = False
if arr[0] == j:
dp[0][j] = True

# Fill the subset table in botton up manner
for i in range(0, n):
for j in range(1, s + 1):
if j < arr[i]: dp[i][j] = dp[i-1][j] if j >= arr[i]:
dp[i][j] = (dp[i-1][j] or dp[i-1][j-arr[i]])

return dp
```

Finding the actual subset that sum up to sum

For this step we will traverse our `dp` table recursively and build the possible paths (path=array containing the elements of the original set that lead to the sum) on the way. We start with the target `sum` and the last element in `array`and move our way backwards. Each time we check if the current element `array[i]`is included in the current sum. At each recursive call we might decrease the target `sum` (by subtracting the current element from it in case it should be included) and we definitely decrease the index of the element we will be considering on our next call. That way we guarantee that our recursion will stop at some point. Either because we reached a `sum <=0` or we have exhausted all elements in our `array`.  We print the current path if:

1. We have have exhausted all elements in our `array` and reached a `sum==0` or
2. We have have exhausted all elements in our `array`, we haven’t reached a `sum==0` yet but the last element in `array` is equal to the remaining `sum`.
```def traverse_dp(arr, dp, s, path, i, all_paths):
if i < 0 or s < 0:
return all_paths

if i == 0 and s != 0 and dp[0][s]:
path.append(arr[i])
all_paths.append(path.copy())
path.clear()
return all_paths

if i == 0 and s == 0:
all_paths.append(path.copy())
path.clear()
return all_paths

# Sum can be achieved without using current element
all_paths_a = all_paths
if dp[i][s]:
new_path = path.copy()
all_paths_a = traverse_dp(arr, dp, s, new_path, i-1, all_paths)

# Sum can be achieved using current element
all_paths_b = all_paths
if arr[i] <= s and dp[i-1][s - arr[i]]:
path.append(arr[i])
all_paths_b = traverse_dp(arr, dp, s-arr[i], path, i-1, all_paths)

ans = all_paths
if len(all_paths_a) != len(all_paths):
ans = all_paths_a

if len(all_paths_b) != len(all_paths):
ans += all_paths_b

return ans

def solve(arr, s):
dp = fill_dp(arr, s)
all_paths = traverse_dp(arr, dp, s, [], len(arr)-1, [])
return all_paths

print(solve([7, 7, 1, 2, 3, 4, 5], 7))
```

This returns:

`[[7], [7], [4, 2, 1], [4, 3], [5, 2]]`