Practice › Recursion & Backtracking
Subset Sums
Medium · Recursion & Backtracking · Asked at Amazon, Microsoft, TCS
Print the sums of all 2^n subsets of the array (including the empty subset, whose sum is 0) in increasing order.
Input
First line: n. Second line: n integers.
Output
All 2^n subset sums in increasing order, space-separated.
Constraints
- 1 ≤ n ≤ 15
- 0 ≤ a[i] ≤ 10^4
For every element choose "take" or "not take" recursively.
Example 1
Input
2 2 3
Output
0 2 3 5
Example 2
Input
3 5 2 1
Output
0 1 2 3 5 6 7 8
Hints
- Every element is either in the subset or not — two choices per element, 2^n subsets in total.
- Recurse with (index, sum so far): one call skips a[index], the other adds it. At index n, record the sum. Sort at the end.
Approach
go(i, sum): if i == n, store sum. Otherwise call go(i + 1, sum) (not take) and go(i + 1, sum + a[i]) (take). The recursion tree has 2^n leaves, one per subset (32 768 for n = 15). Sort the collected sums before printing. The same subsets can also be listed by iterating over bitmasks 0 … 2^n − 1.
Complexity: O(2^n · log 2^n) time (sorting) · O(2^n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
vector<int> sums;
void go(int i, int sum) {
if (i == n) {
sums.push_back(sum);
return;
}
go(i + 1, sum); // don't take a[i]
go(i + 1, sum + a[i]); // take a[i]
}
int main() {
cin >> n;
a.resize(n);
for (auto &x : a) cin >> x;
go(0, 0);
sort(sums.begin(), sums.end());
for (size_t i = 0; i < sums.size(); i++) cout << sums[i] << (i + 1 < sums.size() ? " " : "\n");
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1 : data[0] + 1]
sums = []
def go(i, total):
if i == n:
sums.append(total)
return
go(i + 1, total) # don't take a[i]
go(i + 1, total + a[i]) # take a[i]
go(0, 0)
print(*sorted(sums))Java solution
import java.util.*;
public class Main {
static int n;
static int[] a;
static List<Integer> sums = new ArrayList<>();
static void go(int i, int sum) {
if (i == n) {
sums.add(sum);
return;
}
go(i + 1, sum); // don't take a[i]
go(i + 1, sum + a[i]); // take a[i]
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
a = new int[n];
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
go(0, 0);
Collections.sort(sums);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < sums.size(); i++) sb.append(i > 0 ? " " : "").append(sums.get(i));
System.out.println(sb);
}
}