Sum of Subsets

Introduction

The Sum of Subsets Problem is a classical application of the Backtracking technique. The objective is to determine one or more subsets of a given set whose elements add up exactly to a specified target value.

Instead of checking every possible subset blindly, Backtracking systematically explores different combinations and abandons those branches that cannot produce the required sum.

Problem Statement

Given a set of positive integers and a target value, determine all subsets whose sum is exactly equal to the target value.

Real-Life Example

Suppose a student has currency notes of ₹5, ₹10, ₹12 and ₹13. The student wants to pay exactly ₹22. The objective is to determine which combination of notes produces the required amount.

Why Backtracking?

Every element has only two choices: either it is included in the subset or it is excluded. Whenever the current sum exceeds the required value, the algorithm immediately returns to the previous decision and explores another combination.

Example Data

Solved Example

Find all subsets whose sum is equal to 22.

Required Subset = {10,12}

State Space Tree

                 Start

               /       \

           Include     Exclude

              |

            Include

              |

          Current Sum

          /         \

      Valid      Invalid

        |            X

   Solution

Working Principle

The algorithm starts with an empty subset and processes each element one by one. For every element, it explores two possibilities:

• Include the current element in the subset.
• Exclude the current element from the subset.

Whenever the current sum becomes greater than the target value, that branch is discarded immediately. This pruning significantly reduces the number of combinations explored compared to exhaustive search.

Sum of Subsets Algorithm

Dry Run

Consider the set {5, 10, 12, 13} and the target sum 22.

Complexity Analysis

Advantages of Sum of Subsets

• Produces all valid subsets satisfying the required sum.
• Backtracking avoids unnecessary computations through pruning.
• Simple recursive implementation.
• Suitable for constraint satisfaction problems.
• Can solve multiple subset combinations.

Limitations of Sum of Subsets

• Worst-case execution time is exponential.
• Performance decreases as the number of elements increases.
• Requires recursive function calls.
• Not suitable for very large datasets.

Applications of Sum of Subsets

Sum of Subsets vs 0/1 Knapsack

Summary

The Sum of Subsets Problem is a classical Backtracking problem that determines all subsets whose elements add up to a specified target value. The algorithm recursively explores all possible subsets while pruning branches that cannot produce a valid solution. Although its worst-case time complexity is O(2ⁿ), Backtracking significantly reduces unnecessary exploration through effective pruning.