concept · INFO-CS-ADS-182Subset Sum Problem
Learn how dynamic programming determines whether a subset of given numbers can produce a specified target sum.
Explanation
Overview
The Subset Sum Problem asks whether a subset of a given set of integers exists whose elements add up to a specified target value. Each element can be selected at most once.
Key concepts
Subset selection; Boolean dynamic programming; Include-or-exclude decisions; Reachable sums; Descending iteration
Variables
A: The input array of integers.; i: The number of elements considered.; s: The target sum currently being considered.; dp[i][s]: Whether a subset of the first i elements can produce sum s.
Complexity
tabulation: O(nS) time and O(nS) space.; spaceOptimized: O(nS) time and O(S) space.; variables: n is the number of input elements and S is the nonnegative target sum.
Example
input: 3; 34; target: 9; selectedSubset: 4; 5; output: True; explanation: The subset containing 4 and 5 produces the target sum of 9.
Pseudocode
function subsetSum(A, target):
dp = Boolean array of size target + 1 filled with false
dp[0] = true
for value in A:
for s = target down to value:
dp[s] = dp[s] OR dp[s - value]
return dp[target]
Applications
Partition problems.; Budget allocation.; Resource selection.; Combinatorial optimization.; Cryptographic research and complexity theory.
Variables
A
The input array of integers.
I
The number of elements considered.
S
The target sum currently being considered.
Dp[i][s]
Whether a subset of the first i elements can produce sum s.
Example or application
Explanation
The subset containing 4 and 5 produces the target sum of 9.
Definition
The Subset Sum Problem asks whether a subset of a given set of integers exists whose elements add up to a specified target value. Each element can be selected at most once.
Mathematical Representation
dp[i][s] = dp[i-1][s] OR dp[i-1][s-A[i-1]], when A[i-1] <= s; otherwise dp[i][s] = dp[i-1][s].
Approaches
Recursive
For each element, considers including or excluding it.
Memoization
Stores whether a given remaining sum can be formed using the remaining elements.
Tabulation
Builds a Boolean table of reachable sums.
Space Optimized
Uses a one-dimensional Boolean array and processes sums in descending order so each element is used only once.
Pseudocode
function subsetSum(A, target):
dp = Boolean array of size target + 1 filled with false
dp[0] = true
for value in A:
for s = target down to value:
dp[s] = dp[s] OR dp[s - value]
return dp[target]
Complexity
Tabulation
O(nS) time and O(nS) space.
Space Optimized
O(nS) time and O(S) space.
Variables
n is the number of input elements and S is the nonnegative target sum.
Advantages
Determines whether the target sum is achievable.
Avoids exploring many repeated recursive states.
Can be extended to recover a subset that produces the target.
Forms the basis of several partition and resource-selection problems.
Limitations
The O(nS) algorithm is pseudo-polynomial.
Large target sums may require substantial memory.
The presented one-dimensional implementation assumes nonnegative integers.
Negative numbers require a different state representation.
Practice Question
Can the array [2, 3, 7, 8] produce a subset with sum 10?
Practice Answer
Yes. The subset [2, 8] produces 10.
Learning Objectives
Explain the central idea and purpose of subset sum problem.
Identify the assumptions, inputs, and conditions relevant to subset sum problem.
Evaluate an application of subset sum problem for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Dynamic Programming Applications
Suggest a correction or source · More in Algorithms & Data Structures