Getting everything ready for you…

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

0s

Practice › Recursion & Backtracking

Subsets with Duplicates

Medium · Recursion & Backtracking · Asked at Amazon, Meta, Microsoft, Bloomberg

The array may contain duplicates. Consider all distinct subsets (as multisets — {1,2} and {2,1} are the same). Print how many there are, including the empty subset. Then print every non-empty subset on its own line with its elements in increasing order, with the subsets sorted lexicographically (compare element by element; a proper prefix comes first).

Input

First line: n. Second line: n space-separated integers.

Output

The count, then the non-empty subsets.

Constraints

Sort first. In the recursion, at each level skip an element equal to the previous one at the same level — that avoids generating the same subset twice.

Example 1

Input

3
1 2 2

Output

6
1
1 2
1 2 2
2
2 2

Example 2

Input

1
0

Output

2
0

Hints

  1. Sort the array so equal values are next to each other.
  2. In the recursion "choose the next element from index start onwards", skip a[i] when i > start and a[i] == a[i−1] — the same value at the same level would rebuild the same subsets.

Approach

After sorting, go(start, cur) first records cur (every node of the recursion tree is a subset), then tries each next element a[i] for i ≥ start, skipping duplicates at the same level. Each distinct subset is generated exactly once, already in increasing order, and the DFS order (shorter prefix first, then by value) is exactly the required lexicographic order. The count includes the empty subset.

Complexity: O(2^n · n) time · O(n) recursion depth

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

vector<int> a, cur;
vector<string> out;

void go(int start) {
    if (!cur.empty()) {
        string s;
        for (size_t i = 0; i < cur.size(); i++) s += (i ? " " : "") + to_string(cur[i]);
        out.push_back(s);
    }
    for (int i = start; i < (int)a.size(); i++) {
        if (i > start && a[i] == a[i - 1]) continue;
        cur.push_back(a[i]);
        go(i + 1);
        cur.pop_back();
    }
}

int main() {
    int n;
    cin >> n;
    a.resize(n);
    for (auto &x : a) cin >> x;
    sort(a.begin(), a.end());
    go(0);
    cout << out.size() + 1 << "\n";
    for (auto &s : out) cout << s << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
a = sorted(data[1 : 1 + data[0]])
out = []


def go(start, cur):
    if cur:
        out.append(" ".join(map(str, cur)))
    for i in range(start, len(a)):
        if i > start and a[i] == a[i - 1]:
            continue
        go(i + 1, cur + [a[i]])


go(0, [])
print(len(out) + 1)
if out:
    print("\n".join(out))

Java solution

import java.util.*;

public class Main {
    static int[] a;
    static List<String> out = new ArrayList<>();

    static void go(int start, List<Integer> cur) {
        if (!cur.isEmpty()) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < cur.size(); i++) sb.append(i > 0 ? " " : "").append(cur.get(i));
            out.add(sb.toString());
        }
        for (int i = start; i < a.length; i++) {
            if (i > start && a[i] == a[i - 1]) continue;
            cur.add(a[i]);
            go(i + 1, cur);
            cur.remove(cur.size() - 1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        Arrays.sort(a);
        go(0, new ArrayList<>());
        StringBuilder sb = new StringBuilder();
        sb.append(out.size() + 1).append('\n');
        for (String s : out) sb.append(s).append('\n');
        System.out.print(sb);
    }
}

Solve Subsets with Duplicates online · All practice problems