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; andpath
, 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 bottomup 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
.
 Determines the number of elements in the list

dp = [[False for _ in range(k + 1)] for _ in range(n + 1)]
 Creates a 2D list (matrix)
dp
wheredp[i][j]
will beTrue
if a subset of the firsti
elements ofS
has a sum equal toj
. Initially, all values are set toFalse
.
 Creates a 2D list (matrix)

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
.
 This nested loop iterates over all possible sums from 1 to

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).
 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
Checking for Subset Existence and Constructing the Subset #

if not dp[n][k]: return None
 If the bottomright corner of the matrix is
False
, no subset adds up tok
, so returnNone
.
 If the bottomright corner of the matrix is

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]
isTrue
, 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.
 The while loop
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 listS
.
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: #
 Approach: Dynamic programming vs. Recursion and backtracking.
 Performance:
find_subset_sum
is generally more efficient for larger inputs due to its polynomial time complexity, whilefind_subset
can be faster for smaller inputs but gets exponentially slower as input size increases.  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.