Subset Sum K

December 26, 2023

Problem #

Given a list of integers S and a target number k, write a function that returns a subset of S that adds up to k. If such a subset cannot be made, then return null.

Integers can appear more than once in the list. You may assume all numbers in the list are positive.

Solution 1 #

Here is a Python solution using recursion and backtracking:

def find_subset(candidates, target):
    def _find_subset(idx, target, path):
        if target == 0:
            return [path]
        if idx == len(candidates) or target < 0:
            return []

        # Without the current number.
        res1 = _find_subset(idx + 1, target, path)
        # With the current number.
        res2 = _find_subset(idx, target - candidates[idx], path + [candidates[idx]])
        return res1 + res2

    res = _find_subset(0, target, [])
    if not res:
        return None
    return res[0]

In this solution:

• We first define a helper function _find_subset() that uses recursion and backtracking to find all possible subsets that add up to the target number. It takes three arguments: idx, which is the current index in the input list; target, which is the remaining sum needed to reach the target; and path, which is the current subset being built.
• If the target has been reached, it returns a list containing this subset.
• If we have exhausted all numbers or there are no more numbers that can be used to reach the target, it returns an empty list.
• Otherwise, it first tries to find all subsets without the current number and then tries to find all subsets with the current number.
• The main function find_subset() simply calls this helper function with appropriate arguments and returns its result.

Solution 2 #

Here’s the Python code for the function find_subset_sum which solves the problem of finding a subset of a given list of integers that adds up to a target number:

def find_subset_sum(S, k):
    """
    This function finds a subset of list S that adds up to the target number k.
    If such a subset cannot be made, it returns None.

    :param S: List of positive integers
    :param k: Target sum
    :return: A subset of S that adds up to k or None if no such subset exists
    """
    n = len(S)
    
    # Using a dynamic programming approach to solve the problem
    dp = [[False for _ in range(k + 1)] for _ in range(n + 1)]

    # Initializing the first column as True (sum of 0 is always possible)
    for i in range(n + 1):
        dp[i][0] = True

    # Fill the partition table in bottom-up manner
    for i in range(1, n + 1):
        for j in range(1, k + 1):
            if j < S[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - S[i - 1]]

    # If there's no subset with sum k
    if not dp[n][k]:
        return None

    # Trace back to find the elements in the subset
    subset = []
    i, j = n, k
    while i > 0 and j > 0:
        if dp[i - 1][j]:
            i -= 1
        else:
            subset.append(S[i - 1])
            j -= S[i - 1]
            i -= 1

    return subset

# Example usage
S = [3, 34, 4, 12, 5, 2]
k = 9
result = find_subset_sum(S, k)
print("Subset summing up to", k, ":", result)

This code uses a dynamic programming approach to efficiently find a subset of S that sums up to k. If there’s no such subset, it returns None. You can use this function with any list of positive integers and a target sum. The example usage provided will output the subset that sums up to 9 from the given list.

Solution 2 analysis #

The provided Python function find_subset_sum solves the subset sum problem using a dynamic programming approach. Here’s a breakdown of how the code works:

Function Definition #

• def find_subset_sum(S, k):
  • S is the list of integers.
  • k is the target sum.

Dynamic Programming Table Initialization #

• n = len(S)

  • Determines the number of elements in the list S.

• dp = [[False for _ in range(k + 1)] for _ in range(n + 1)]

  • Creates a 2D list (matrix) dp where dp[i][j] will be True if a subset of the first i elements of S has a sum equal to j. Initially, all values are set to False.

• First column initialization:

  • for i in range(n + 1): dp[i][0] = True
  • This sets the first column to True because a sum of 0 is always achievable (with an empty subset).

Dynamic Programming to Fill the Table #

• for i in range(1, n + 1):

  • This loop iterates over the elements of the list.

• for j in range(1, k + 1):

  • This nested loop iterates over all possible sums from 1 to k.

• if j < S[i - 1]: dp[i][j] = dp[i - 1][j]

  • If the current element is larger than the sum we are trying to achieve, we just carry over the value from the previous row (i.e., excluding the current element).

• else: dp[i][j] = dp[i - 1][j] or dp[i - 1][j - S[i - 1]]

  • Otherwise, we check if we can achieve the sum either by excluding the current element (carry over the value) or by including it (check if the sum j - S[i - 1] was achievable with the previous elements).

Checking for Subset Existence and Constructing the Subset #

• if not dp[n][k]: return None

  • If the bottom-right corner of the matrix is False, no subset adds up to k, so return None.

• subset = []

  • Initialize an empty list to store the elements of the found subset.

• Backtracking to find the subset elements:

  • The while loop while i > 0 and j > 0: traces back the elements included in the subset.
  • If dp[i - 1][j] is True, it means the current element was not included in the sum, so we move to the previous element.
  • Otherwise, we include the current element in the subset, reduce the target sum by the value of the current element, and move to the previous row.

Example Usage #

• The example at the end of the function demonstrates how to use it. It prints out the subset that sums up to the target k from the given list S.

This code effectively solves the subset sum problem for positive integers and returns a valid subset if it exists. If no subset can be found that sums up to the target value, it returns None.

Solution Comparison #

Both the provided solution and the earlier find_subset_sum function aim to solve the same problem—finding a subset of a given list of integers that adds up to a target number—but they approach it in different ways. Let’s compare the two solutions:

1. The find_subset_sum Function: #

• Approach: It uses dynamic programming.
• Space Complexity: It creates a 2D array (dp), so the space complexity is O(n*k), where n is the number of elements in the list, and k is the target sum.
• Time Complexity: Similar to space complexity, it is O(n*k).
• Behavior: It returns one subset that sums up to the target value. The subset is obtained by backtracking through the dp array.
• Limitations: It doesn’t find all possible subsets, just one. Also, it requires additional space for the dp array.

2. The find_subset Function: #

• Approach: It uses recursion and backtracking.
• Space Complexity: The space complexity mainly depends on the call stack due to recursion, which can go up to O(n) in the worst case.
• Time Complexity: It’s O(2^n) in the worst case because it explores two possibilities for each element (including or excluding it).
• Behavior: This function returns one subset that sums up to the target value, but it’s capable of finding all possible subsets (although currently, it only returns the first found). It explores both including and excluding each element.
• Limitations: It can be slower for large input sizes due to its exponential time complexity. Also, it may face stack overflow issues for very large inputs because of deep recursion.

Key Differences: #

1. Approach: Dynamic programming vs. Recursion and backtracking.
2. Performance: find_subset_sum is generally more efficient for larger inputs due to its polynomial time complexity, while find_subset can be faster for smaller inputs but gets exponentially slower as input size increases.
3. Use Case: find_subset_sum is more suited for situations where space is not a major concern, and you need one valid subset. In contrast, find_subset can be adapted to find all possible subsets but may be less practical for very large inputs.

In summary, if you need a more efficient solution for larger inputs and only need one subset, find_subset_sum is more appropriate. However, if you want to explore all possible subsets for smaller inputs, find_subset is more suitable.