Create a solution for the subset sum problem using dynamic programming.
- User
Create a solution for the subset sum problem using dynamic programming.
- Assistant
Creating a subset sum solution
The user requested a solution for the subset sum problem using dynamic programming, likely wanting a clear algorithm description and possibly some code. I'll choose Python as the programming language, and keep it concise yet informative—balancing detail with brevity.
I’ll outline the problem briefly, describe the dynamic programming approach, state the time and space complexity, and provide Python code. Additionally, it would be nice to mention how to reconstruct the subset, but I’ll keep it minimal since they didn't explicitly ask for that.Implementing subset sum in Python
I've crafted a Python function called
subset_sumto solve the subset sum problem. It creates a 2D dynamic programming table to determine if a subset of given numbers sums to a target. If a solution exists, it can also reconstruct the subset.The time and space complexity is O(n*target), but I can optimize it to O(target) if I only need a boolean outcome. Now, I should put this all together in a clear presentation. Here’s a dynamic programming solution to the Subset Sum problem.
Problem
Given:
- A list of integers
nums - A target sum
target
Determine whether there exists a subset of
numswhose elements sum totarget. Optionally, reconstruct such a subset.
Dynamic Programming Idea
State
Let
dp[i][s]be a boolean:Trueif we can form sumsusing the firstielements ofnumsFalseotherwise
Recurrence
For each element
nums[i-1](sinceiis 1-based indp):- We can exclude it:
dp[i][s] = dp[i-1][s] - If
s >= nums[i-1], we can also choose to include it:
dp[i][s] = dp[i][s] or dp[i-1][s - nums[i-1]]
So:
dp[i][s] = dp[i-1][s] or (s >= nums[i-1] and dp[i-1][s - nums[i-1]])Base Case
dp[0][0] = True(using 0 elements we can make sum 0: take empty subset)dp[0][s] = Falsefor alls > 0
Answer
- The target is achievable if
dp[n][target]isTrue, wheren = len(nums).
Implementation in Python (with subset reconstruction)
def subset_sum(nums, target): n = len(nums) # dp[i][s] is True if sum 's' can be formed using first i elements dp = [[False] * (target + 1) for _ in range(n + 1)] # Base case: sum 0 is always achievable (empty subset) dp[0][0] = True # Fill DP table for i in range(1, n + 1): current = nums[i - 1] for s in range(target + 1): # Option 1: exclude current element dp[i][s] = dp[i - 1][s] # Option 2: include current element (if possible) if s >= current and dp[i - 1][s - current]: dp[i][s] = True # If no subset yields the target sum if not dp[n][target]: return False, [] # Reconstruct one subset that gives the target sum subset = [] s = target i = n while i > 0 and s >= 0: # If this row differs from the row above, nums[i-1] was used if dp[i][s] and not dp[i - 1][s]: subset.append(nums[i - 1]) s -= nums[i - 1] i -= 1 subset.reverse() # optional, to get the original order return True, subset # Example usage: nums = [3, 34, 4, 12, 5, 2] target = 9 exists, subset = subset_sum(nums, target) print("Exists:", exists) # True print("Subset:", subset) # e.g. [4, 5]
Complexity
- Time:
O(n * target) - Space:
O(n * target)
If you only need the boolean answer (not the actual subset), you can optimize to
O(target)space using a 1D DP array; I can show that variant if you’d like. - A list of integers
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.