# Subset Sum (Sum Subset) — Backtracking with Pruning in C++ ## Introduction The Subset Sum problem asks whether there exists a subset of a given set of numbers whose sum equals a target value M. The repository implements a backtracking (branch-and-bound) solution that uses sorting and a running remainder bound to prune the search space effectively. Reference implementation: https://github.com/mashrur-rahman-fahim/algorithm/blob/main/sum_subset.cpp. --- ## Approach (branch-and-bound) 1. Sort the input array ascending. Sorting helps bound checks be more effective. 2. Maintain: - s — current sum of elements chosen so far. - k — current index in recursion. - r — sum of remaining elements not yet considered (used for bounding). - x — binary selection vector where x[i] = 1 means a[i] is chosen. 3. At each step try including a[k] (x[k] = 1) and recurse; after returning, try excluding it (x[k] = 0) only if it's still possible to reach target with remaining elements. The repository uses two bounding tests to prune branches early: - If s + a[k] == M we found a solution. - If s + a[k] + a[k+1] <= M we can still try to add next items after including a[k]. - If s + r - a[k] >= M and s + a[k+1] <= M then excluding a[k] still leaves hope. --- ## Why sorting helps With ascending order, the remainder r and quick feasibility checks become tighter: when the smallest remaining elements can't reach the target, larger ones won't either, so branches can be pruned earlier. --- ## Example Input array: a = [3, 34, 4, 12, 5, 2], target M = 9. After sorting: [2, 3, 4, 5, 12, 34]. Solutions found include subsets like {4, 5} and {2, 3, 4} (those sum to 9). The implementation prints binary selection vectors x[0..k] showing which elements were selected for each solution. --- ## Complexity - Worst-case complexity is exponential: O(2^N) — any backtracking subset-sum algorithm can hit exponential behavior. - Practical performance is often much better due to pruning and bounding. --- ## Improvements & alternatives 1. Dynamic Programming: DP gives O(N·M) time and is ideal when M is not too large. 2. Bitset trick: using bitset shifts to compute reachable sums in O(N · (M/word_size)) time but with much smaller constants. 3. Meet-in-the-middle: split the set into two halves, enumerate sums for each half and combine with sorting — runs in O(2^(N/2)) and is practical for N ~ 40. 4. Memoization: store partial states (k, s) to avoid revisiting the same states — trades memory for time. --- ## Implementation notes (from repository) - The code sorts the input and computes an initial total sum for r. - It uses recursion with x[k] assigned 1 (take) and 0 (skip) and prints when a valid solution is reached. - Because the code prints selection vectors, mapping them back to the original (unsorted) indices requires extra bookkeeping if that is desired. --- Repository: https://github.com/mashrur-rahman-fahim/algorithm/blob/main/sum_subset.cpp Images (use in article): 1. https://www.shutterstock.com/image-photo/programmer-cyber-security-technology-male-600nw-2464110045.jpg 2. https://www.snexplores.org/wp-content/uploads/2020/11/1030_algorithm_explainer-1028x579.jpg 3. https://i0.wp.com/bdtechtalks.com/wp-content/uploads/2022/02/algorithm-formulation.jpg?ssl=1