Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Every element is either in the subset or not — two choices per element, 2^n subsets in total.
  2. 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);
    }
}

Solve Subset Sums online · All practice problems