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 asum==0
or - We have have exhausted all elements in our
array
, we haven’t reached asum==0
yet but the last element inarray
is equal to the remainingsum
.
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]]