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
- 1 ≤ n ≤ 12
- -10 ≤ a[i] ≤ 10
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
- Sort the array so equal values are next to each other.
- 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