Sum of Sub-Sets Problem using Backtracking

In this article, we will solve Subset Sum problem using a backtracking approach which will take O(2^N) time complexity but is significantly faster than the recursive approach which take exponential time as well.

Subset sum problem is the problem of finding a subset such that the sum of elements equal a given number. The backtracking approach generates all permutations in the worst case but in general, performs better than the recursive approach towards subset sum problem.

A subset A of n positive integers and a value sum is given, find whether or not there exists any subset of the given set, the sum of whose elements is equal to the given value of sum.

---

Example

---

Given a set X of positive integers and target integer T, is there a subset of elements in X that add up to T? Notice that there can be more than one such subset.

For example, if X = {8, 6, 7, 5, 3, 10, 9} and T = 15, the answer is TRUE, thanks to the subsets {8, 7} or {7, 5, 3} or {6, 9} or {5, 10}.

On the other hand, if X = {11,6,5,1,7,13,12} and T = 15, the answer is FALSE.

---

Algorithm and Complexity

---

There are two trivial cases. If the target value T is zero, then we can immediately return TRUE, because the elements of the empty set add up to zero. On the other hand, if T < 0, or if T != 0 but the set X is empty, then we can immediately return FALSE.

For the general case, consider an arbitrary element x ∈ X. There is a subset of X that sums to T if and only if one of the following statements is true:

• There is a subset of X that includes x and whose sum is T.
• There is a subset of X that excludes x and whose sum is T.

In the first case, there must be a subset of X \ {x} that sums to T - x; in the second case, there must be a subset of X \ {x} that sums to T. So we can solve SUBSETSUM(X, T) by reducing it to two simpler instances: SUBSETSUM(X \ {x}, T - x) and SUBSETSUM(X \ {x}, T). Here's how the resulting recusive algorithm might look if X is stored in an array.

---

The running time T(n) clearly satisfies the recurrence T(n) ≤ 2T(n - 1) + O(1), so the running time is T(n) = O(2^n) by the annihilator method.

Here is a similar recursive algorithm that actually constructs a subset of X that sums to T, if one exists. This algorithm also runs in O(2^n) time.

---

---

Happy Exploring!