Q6Design and Analysis of Algorithms
Question
4 marks
Describe the Subset Sum problem using Backtracking.
Answer
Subset Sum problem finds subsets summing to a target value using backtracking to prune invalid branches early.
The Subset Sum Problem: Given a set S = {s₁, s₂, ..., sₙ} of positive integers and a target sum T, find all subsets of S whose elements sum exactly to T. This is NP-Complete.
- Sort the set in non-decreasing order for efficient pruning.
- Build a subset tree: at each node, decide to include or exclude the current element.
- Include element sᵢ: if current_sum + sᵢ == T, print solution; if current_sum + sᵢ < T, recurse for sᵢ₊₁.
- Exclude element sᵢ: if current_sum + sᵢ₊₁ ≤ T, recurse without including sᵢ.
- Bounding: prune if current_sum > T (too large) or current_sum + remaining_sum < T (too small).
S = {3, 5, 6, 7}, T = 15. Sort: {3, 5, 6, 7}. Include 3: recurse {5,6,7} with sum=3. Include 5: recurse {6,7} with sum=8. Include 6: sum=14 < 15. Include 7: sum=21 > 15 → backtrack. Exclude 6: include 7, sum=15 → Solution: {3,5,7}. Found! The algorithm prunes many branches, making it efficient in practice.