# 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:

- We have have exhausted all elements in our
`array`

and reached a`sum==0`

or - 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]]