📘 Subset–Sum Problem

1️⃣ Introduction

The Subset–Sum Problem is a classical problem in algorithm design and computational complexity.

🔹 Definition

Given a set of n positive integers and a target value S, determine whether there exists a subset whose sum is exactly S.

The subset may contain any number of elements from the given set.

2️⃣ Problem Statement

Given:

A set of integers:
[
A = {a_1, a_2, a_3, \dots, a_n}
]
A target sum: S

Determine whether:
[
\sum_{i \in subset} a_i = S
]

3️⃣ Nature of the Problem

Decision problem (Yes/No answer)
Belongs to the class of NP-Complete problems
Used as a base problem for proving NP-completeness of other problems

4️⃣ Approaches to Solve Subset–Sum

🔹 1. Brute Force

Try all possible subsets (2ⁿ)
Very inefficient

Time Complexity: O(2ⁿ)

🔹 2. Backtracking (Preferred for Teaching)

Build solution incrementally
Prune branches when:
- Sum exceeds target
- No feasible solution remains

🔹 3. Dynamic Programming

Converts exponential time to pseudo-polynomial time
Guarantees optimal solution

5️⃣ Subset–Sum Using Backtracking

🔹 Basic Idea

At each step, decide:

Include current element
Exclude current element

If partial sum:

Equals S → solution found
Exceeds S → backtrack

6️⃣ State Space Tree Concept

Each level represents an element
Left branch → include element
Right branch → exclude element
Invalid paths are pruned early

7️⃣ Algorithm (Backtracking Approach)

🔹 Pseudocode

SubsetSum(i, current_sum):
   if current_sum == S:
       print subset
       return true
   if i == n or current_sum > S:
       return false

   // Include element
   if SubsetSum(i+1, current_sum + a[i]):
       return true

   // Exclude element
   if SubsetSum(i+1, current_sum):
       return true

   return false

8️⃣ Example

🔹 Given:

Set = {10, 7, 5, 18, 12, 20, 15}
Target Sum = 35

🔹 One Possible Subset:

[
{10, 5, 20}
]

✔ Sum = 35

9️⃣ Time and Space Complexity

🔹 Backtracking

Time Complexity: O(2ⁿ) (worst case)
Space Complexity: O(n) (recursion stack)

🔹 Dynamic Programming

Time Complexity: O(nS)
Space Complexity: O(nS)

🔟 Subset–Sum Using Dynamic Programming

🔹 DP Table

dp[i][j] = true if sum j is possible using first i elements

🔹 Recurrence Relation

[
dp[i][j] =
\begin{cases}
dp[i-1][j] \quad \text{or} \quad dp[i-1][j-a_i] & j \ge a_i \
dp[i-1][j] & j < a_i
\end{cases}
]

1️⃣1️⃣ Applications

Resource allocation
Cryptography
Budget planning
Partition problem
Knapsack problem

1️⃣2️⃣ Advantages and Limitations

✔ Advantages

Backtracking prunes invalid subsets
DP provides guaranteed solution

✖ Limitations

Backtracking is exponential
DP is memory-intensive

🔚 Conclusion

The Subset–Sum Problem is a foundational NP-Complete problem that demonstrates the power of backtracking and dynamic programming in solving combinatorial problems.

Subset–Sum explores whether a target can be formed by selecting a subset of given numbers.

Subset – Sum Problem