Sum of Subsets Problem in DAA

Learn the Sum of Subsets Problem in DAA using Backtracking. Understand the algorithm, state space tree, pruning conditions, time complexity O(2ⁿ), examples, and real-world applications.

Sum of Subsets Problem in DAA-

Introduction

The Sum of Subsets Problem is a Backtracking-based problem.
From a given set of positive numbers, we have to select certain elements such that their sum is equal to a given target value (W).

Problem Statement

Given a set:
S = { w₁, w₂, w₃, … , wₙ }

Given target sum:
W

Objective:
Find all subsets such that

∑wi=W\sum w_i = W∑wi=W

Example

Given set:
S = { 10, 7, 5, 18, 12, 20, 15 }
Target Sum:
W = 35

Valid subsets are:

{ 10, 7, 18 } → 35
{ 20, 15 } → 35

Concept of Backtracking

For each element, there are two possible choices:
- Include the element
- Exclude the element
If the current sum exceeds W, further exploration is stopped (Pruning)

State Space Tree

Each level of the tree represents one element
Left branch → element is included
Right branch → element is excluded

Sum of Subsets Algorithm (Backtracking)

SumSubset(i, current_sum)
{
if (current_sum == W)
print subset
else if (current_sum < W and i ≤ n)
{
// Include element
SumSubset(i + 1, current_sum + w[i])

// Exclude element
SumSubset(i + 1, current_sum)
}
}

Bounding (Pruning) Conditions

To reduce unnecessary computation in backtracking:

If current_sum > W → Stop
If current_sum + sum of remaining elements < W → Stop

Time Complexity

Worst Case Time Complexity: O(2ⁿ)
Because each element has two choices (include or exclude)

Space Complexity

O(n) – Recursive call stack
O(n) – To store the current subset

Advantages of the Sum of Subsets Problem

Useful for solving subset selection problems
Helps in understanding backtracking and pruning techniques
Forms the basis for many optimization problems

Limitations

Takes a large amount of time for large values of n
The problem belongs to the NP-Complete category

Applications

Resource Allocation
Budget Planning
Load Balancing
Basis for the Knapsack Problem

Conclusion

The Sum of Subsets Problem is an effective example of the Backtracking method.
It clearly demonstrates the limitations of algorithmic power when dealing with complex and combinatorial problems.

Some More:

Sum of Subsets Problem in DAA-

Introduction

Problem Statement

Concept of Backtracking

State Space Tree

Bounding (Pruning) Conditions

Advantages of the Sum of Subsets Problem

By Mr. Santosh Nalawade