Here we will describe the exhaustive search algorithm to solve the Subset Sum problem.
The exhaustive search algorithm for the Subset Sum problem generates and checks all possible subsets of the input set to determine whether any of them sum to a given target value \( T \). Since a set of size \( n \) has \( 2^n \) subsets, the algorithm examines each one in turn.
There are many ways of generating all subsets. Here we will describe an algorithm that involves using binary masks. The subsets are generated by iterating over all binary masks of length \( n \), where each bit indicates whether the corresponding element is included (1) or excluded (0) from the subset. For each mask, the algorithm constructs the corresponding subset, computes its sum, and checks whether the sum equals \( T \).
| Index | Bitmask | Subset | Sum | Matches Target? |
|---|---|---|---|---|
| 0 | 000 | \(\{\}\) | 0 | No |
| 1 | 001 | \(\{2\}\) | 2 | No |
| 2 | 010 | \(\{5\}\) | 5 | No |
| 3 | 011 | \(\{2, 5\}\) | 7 | No |
| 4 | 100 | \(\{8\}\) | 8 | No |
| 5 | 101 | \(\{2, 8\}\) | 10 | Yes |
| 6 | 110 | \(\{5, 8\}\) | 13 | No |
| 7 | 111 | \(\{2, 5, 8\}\) | 15 | No |
In general, the algorithm proceeds as follows:
The following demo shows the algorithm in action.
These implementations generate all \( 2^n \) subsets using bitmasks and print any subset whose elements sum to the target value.
void subsetSum(int[] S, int T) {
int n = S.length;
int total = 1 << n; // 2^n
for (int mask = 0; mask < total; mask++) {
int sum = 0;
List<Integer> subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
subset.add(S[i]);
sum += S[i];
}
}
if (sum == T) {
System.out.println(subset);
}
}
}
void subsetSum(int S[], int n, int T) {
int total = 1 << n; // 2^n
int* subset = new int[n];
for (int mask = 0; mask < total; mask++) {
int sum = 0, k = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
subset[k++] = S[i];
sum += S[i];
}
}
if (sum == T) {
cout << "{ ";
for (int j = 0; j < k; j++) {
cout << subset[j] << " ";
}
cout << "}" << endl;
}
}
}def subset_sum(S, T):
n = len(S)
for mask in range(1 << n):
subset = []
total = 0
for i in range(n):
if mask & (1 << i):
subset.append(S[i])
total += S[i]
if total == T:
print(subset)Time Complexity: An input set of size \( n \) has \( 2^n \) subsets. The algorithm loops through all bitmasks from \( 0 \) to \( 2^n - 1 \), and for each mask, it checks which elements are included and computes the sum of the corresponding subset. The inner loop runs in \( O(n) \) time per subset, so the total time complexity is \(O(n \cdot 2^n).\) This is optimal for exhaustive enumeration, since there are \( 2^n \) subsets and each one may contain up to \( n \) elements.
Space Complexity: The algorithm uses \( O(n) \) extra space to store the current subset being considered. No recursion is used, and only a few additional local variables. The total space used is \(O(n)\). If the algorithm also stores all matching subsets, then the output space could be as large as \( O(k \cdot n) \), where \( k \) is the number of solutions.
mask from 0 to 7:
(mask & (1 << i)) and explain whether element \( S[i] \) is included.(mask & (1 << i)) relate to inclusion of each element?