✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-182

Subset 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

Input

  • 3

  • 34

  • 4

  • 12

  • 5

  • 2

Target

9

Selected Subset

  • 4

  • 5

Output

Yes

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.

Key Concepts

  • Subset selection

  • Boolean dynamic programming

  • Include-or-exclude decisions

  • Reachable sums

  • Descending iteration

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.

Applications

  • Partition problems.

  • Budget allocation.

  • Resource selection.

  • Combinatorial optimization.

  • Cryptographic research and complexity theory.

Related Topics

  • 0/1 Knapsack Problem

  • Dynamic Programming

  • Partition Equal Subset Sum

  • Combinatorial Optimization

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