Abstract / Summary

Given a list of numbers that may contain duplicates find all possible subsets without duplicate subsets.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 62% (2+ million submissions).

Typical patterns to solve this problem:

• Array
• Backtracking
• Bit Manipulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method subsetsWithDup that returns all possible subsets of an input list nums, ensuring that duplicate subsets are omitted. The algorithm first sorts the input to bring equal elements together, then iteratively builds new subsets by extending existing ones with each element. A membership test prevents the insertion of duplicate subsets into the final result.

Key Steps

Sorting the Input

nums.sort()

Sorting arranges identical numbers consecutively, which simplifies the detection of duplicate subsets later in the process. By operating on a deterministic order, the method guarantees that subsets generated from equal values will appear in the same sequence, making the duplicate-check reliable.

Initial Result Container

result = [[]]

The algorithm starts with the empty subset, which is a required element of the power set. This container will be expanded in place as the method processes each number.

Generating Candidate Subsets

for i in nums:
    next = []
    for j in result:
        next.append(j + [i])

For each element i in the sorted list, a temporary list next is created. The inner loop iterates over every subset currently stored in result and produces a new subset by appending i. This step systematically explores all combinations that include the current element.

Filtering Duplicates

    for j in next:
        if j not in result:
            result.append(j)

After candidate subsets are generated, each candidate j is examined to see whether it already exists in result. The if j not in result guard eliminates any subset that would be a duplicate, which can arise when the input contains repeated numbers. Only unique subsets are appended to result.

Returning the Complete Set

return result

When all numbers have been processed, result holds the empty subset together with every distinct subset derived from the input list, and it is returned to the caller.

Edge Cases Handled

When the input list is empty, the initial result containing only the empty subset remains unchanged, and the method correctly returns [[]].

If the input consists solely of identical numbers, the sorting step groups them together, and the duplicate-filtering loop ensures that subsets differing only by the count of identical elements are not repeated. For example, with nums = [2, 2], the algorithm yields [[], [2], [2, 2]] without producing duplicate [2] entries.

The membership test j not in result works for any subset length, guaranteeing that even complex duplicates arising from multiple repeated values are excluded.

Performance Optimizations Observed

The algorithm leverages the fact that the list result grows incrementally; each iteration only processes the subsets that existed before the current element is considered. By constructing a separate next list, the method avoids modifying result while it is being iterated, which prevents inadvertent re-processing of newly added subsets within the same outer loop iteration.

Using the built-in list.append operation to add new subsets is efficient because it operates in amortized constant time. The early duplicate check (if j not in result) prevents unnecessary growth of result, reducing the number of elements that must be examined in subsequent iterations.

Sorting the input once at the beginning incurs a one-time cost but yields a deterministic order that simplifies duplicate detection, eliminating the need for more complex data structures such as hash sets for tracking seen subsets. This choice keeps the memory footprint modest, as only the final list of unique subsets and a temporary list for the current iteration are stored.

Imagine you have a box of mixed-up building blocks, and some of them look exactly the same. You want to see every possible group you can build using those blocks.

First, you organize all the blocks by putting them in a straight line from smallest to largest so they are easy to count. You start with an empty tray where you can put your groups.

Now, you look at each block one by one. For every block you hold, you go over to your tray and look at all the groups you have already built. You take each existing group, add your new block to it, and that makes a brand new group.

Since some blocks look the same, you might accidentally make a group that you already have on your tray. Before putting a new group down, you check to see if it is already there. If it is a new, unique group that you have not seen before, you place it on your tray. By the time you finish looking at every single block in your pile, your tray will be filled with every possible combination of blocks you could make.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: exponential
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java								TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	C#	Rust	JS				Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei					Rust
	begeekmyfriend							C
	BigEggStudy				C#
	black-shadows	C++
	bujosa		Python
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	everthis						JS
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost										Go
	haoel			Java
	JoshCrozier						JS
	keineahnung2345	C++
	lennylxx	C++
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	martianoff								Scala
	qiyuangong		Python
	ruoru					Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	varunu28			Java
	vli02							C
	vthwang			Java
	wisdompeak	C++
	XiaotaoGuo	C++
	yuanliu666									Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	Java
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C++
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
martianoff	Scala
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality