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