What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Backtracking & State Search

Builds on Subsets, which you haven’t finished yet.

P2MediumBuilt on Subsets~4 min speedrun

Subsets with Duplicates (Sibling Deduplication)

Built on

SubsetsSort first, then skip a value that equals its left neighbour unless it is the first choice of its call, so no subset is saved twice.

The problem

Subsets II (LC 90)(opens leetcode.com)

Given an integer array nums that may hold duplicate values, produce the full power set -- every possible subset, including the empty subset and the full array itself.

Because nums can repeat values, two different index choices might describe the same subset of values; the returned list must not contain that subset twice. Return the subsets in any order.

Example 1

Input:nums = [1,2,2]

Output:[[],[1],[1,2],[1,2,2],[2],[2,2]]

Picking the first 2 or the second 2 gives the same subset, so [2] and [1,2] appear only once.

Subsets II

sorted elements ➔ skip an equal left neighbour ➔ each distinct subset once

Spot it when: You must list all subsets, and the input has repeated values, so the same subset must not be saved twice.

Subsets II

Python

1	from typing import List
2
3	def subsetsWithDup(nums: List[int]) -> List[List[int]]:
4	"""Subsets II (LC 90): every different subset of nums, saved once at the node of the decision tree that builds it.
5	Sort nums first, then skip nums[i] when i > start and nums[i] == nums[i - 1].
6	N = len(nums). The skip test costs O(1).
7	Time: O(N * 2^N) \| Space: O(N) path + recursion stack, output not counted
8	"""
9	nums.sort() # sort so equal values sit next to each other, needed for the skip test below
10	results: List[List[int]] = []
11	path: List[int] = [] # the choices from the root to the current node, in order
12
13	def backtrack(start: int) -> None:
14	# 1. Save This Node:
15	# Every node of the decision tree is a valid subset, so copy path into results
16	# as soon as the call starts, before trying any further choice.
17	results.append(list(path))
18
19	for i in range(start, len(nums)):
20	# 2. Skip a Repeated Sibling:
21	# nums is sorted, so two equal values sit next to each other; i > start means
22	# nums[i] is not the first choice tried at this level, so skip it to avoid
23	# building the same subset twice.
24	if i > start and nums[i] == nums[i - 1]:
25	continue
26
27	# 3. Choose, Explore, Un-choose:
28	# Add nums[i] to path, recurse forward so the next call only sees later
29	# indices, then remove nums[i] so the loop's next i tries its own branch.
30	path.append(nums[i])
31	backtrack(i + 1)
32	path.pop()
33
34	backtrack(0)
35	return results

Invariant: path always holds exactly the choices from the root to the current node, and no value is tried twice among the choices of one call, so every different subset is saved exactly once.

With repeated values, two different indices can build the same subset, so sort nums and skip nums[i] when i > start and it equals nums[i - 1]: that value was already tried as the choice at this level. After the sort, equal values sit next to each other, so a comparison with the left neighbour finds every repeat. The trap is writing i > 0 instead of i > start: it also skips the second 1 after the first 1 is already in path, so [1, 1] is never built.

See it run

Subsets with duplicates, step by step

start 0path []saved 0

The top row is nums. The middle row is 1 when the item is in path. The bottom row is path, filled from the left.

i the index the loop is looking at
start the first index this call may use
i = start the loop index is the first index of this call
path the slot just added to path
undo the slot just removed from path

nums is sorted: [1, 2, 2]. path is empty, and backtrack(0) is about to run.

nums

1start

in path

path

1 / 20

Gotchas1 of 3

The trap
Gotcha 1: Writing i > 0 instead of i > start
Mistake
```
if i > 0 and nums[i] == nums[i - 1]:
```
Fix
```
if i > start and nums[i] == nums[i - 1]:
```
What happens: The skip test must skip a repeated value only among the choices of one call. With i > 0, the call backtrack(1) also skips the second 1. That call is the only way to put the second 1 after the first one. So [1, 1] and [1, 1, 2] are never built.
Example: nums = [1, 1, 2]
Mistake: returns [[], [1], [1, 2], [2]]Fix: returns [[], [1], [1, 1], [1, 1, 2], [1, 2], [2]]
Gotcha 2: Skipping duplicates without sorting nums first
Mistake
```
results: List[List[int]] = []
```
Fix
```
nums.sort()
results: List[List[int]] = []
```
What happens: The skip test compares nums[i] only with its left neighbour nums[i - 1]. Without the sort, two equal values can sit apart. The test then misses them, and the same subset is saved twice.
Example: nums = [2, 1, 2]
Mistake: returns [[], [2], [2, 1], [2, 1, 2], [2, 2], [1], [1, 2], [2]]Fix: returns [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
Gotcha 3: Sorting nums when the order of the values matters
Mistake
```
nums.sort()
```
Fix
```
used = set()  # values already tried in this call
if nums[i] in used:
    continue
used.add(nums[i])
```
What happens: Non-decreasing Subsequences (LC 491) asks for subsequences in the original order. Sorting nums creates subsequences that do not exist in the input. Keep the order, and skip a repeated value with a used set. Each call creates its own used set, so it only skips repeats among the choices of that call.
Example: Non-decreasing Subsequences (LC 491): nums = [3, 1]
Mistake: returns [[1, 3]]Fix: returns []

Not this one if…

All values are different, as in Subsets (LC 78), so no value can repeat a subset and no skip test is needed. See Subsets
The order matters and every element is used once, as in Permutations II (LC 47): the loop restarts at 0 and the skip test also needs the used array. See Permutations

Deep Dive

Skipping a repeated value: sort, then compare with the left neighbour

Take nums = [1, 2, 2]. The two 2s are different indices, so the plain tree builds [1, 2] twice and [2] twice. That is 8 nodes and 8 saved lists, and 2 of them are repeats.

The fix is the test i > start and nums[i] == nums[i - 1]. It needs a sorted nums, so that equal values sit next to each other. The test says: this value was already tried as the pick at this level, so try the next value.

i > start is the important half. It lets the first value of a level through. At backtrack(2) in the board, i = 2 is not above start = 2, so nums[2] = 2 is chosen and [1, 2, 2] is built. With i > 0, this pick would be skipped, and [1, 2, 2] and [2, 2] would be lost.

With the test, [1, 2, 2] makes 6 calls and returns [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]. This is the example of Subsets II (LC 90).

The cost: nodes times the copy

The tree has one node per subset, so N different numbers give 2^N nodes. Each node copies path, which costs up to O(N). The time is O(N * 2^N), and the call stack is O(N) deep. The saved lists are the output and are not counted.

For N = 20 different numbers, backtrack runs 1,048,576 times. The skip test costs O(1) after the sort, so it does not change this. The sort costs O(N log N) and is small next to 2^N.

Repeated values make the tree smaller, not larger. [1, 2, 2] has 6 nodes, not 8.

60-Second Pitch

"Every node of the decision tree is a valid subset, so I save a copy of path when backtrack starts. The loop picks only indices from start onward, and the recursion goes to i + 1, so each subset is built in one order. The input has repeated values, so I sort first. At each level I skip nums[i] when i > start and it equals nums[i - 1], because that value was already tried at this level. There are at most 2^N nodes, and each copies path in O(N). So the time is O(N * 2^N), and the stack is O(N) deep."

Common Questions

Why do you save path at every call and not only when the index reaches the end?: Every path is already a valid subset, including the empty list at the first call. A save at the end would find only the subsets that use the last index. Saving at every node finds all of them, and each exactly once.
Why is the test i > start and not i > 0?: i > start skips a value only when an equal value was already the pick of this same call. i > 0 also skips the first pick of a call when the previous element is equal, and that pick is needed. For [1, 1, 2], i > 0 loses [1, 1] and [1, 1, 2].
What is the time and space complexity?: O(N * 2^N) time, because there are up to 2^N nodes and each one copies path in up to O(N). The space is O(N) for path and the recursion stack. The output is not counted. The sort adds O(N log N).
How does the answer change if the order inside a subset matters?: Then the problem is about orderings, not subsets. The loop restarts at 0 in every call and uses a used array, as in Permutations (LC 46). Subsets II (LC 90) and Permutations (LC 46) use the same choose, explore, undo structure and differ only in which indices the loop may try.
Why can you not sort the input for Non-decreasing Subsequences (LC 491)?: That problem asks for subsequences, which keep the original order. After sorting, a group such as [4, 6] can appear even when 6 comes before 4 in the input. Keep the order, and in each call skip a value that is already in a used set made for that call.

SWE Reasoning

Spot it

The statement asks for all subsets, all subsequences, or all on/off choices. The answer is a list of lists, not one number.
Every group is valid, including the empty group, so you save at every node and not only at a leaf.
The order inside a group does not matter. [1, 2] and [2, 1] count as one answer.
The input can hold equal values, and the answer must not list the same group twice. This is Subsets II (LC 90).
The input is small, usually 20 items or fewer, because the answer has up to 2^N groups.

The invariant, step by step

backtrack(start) is called with path holding the choices from the first call to this call. The first thing it does is results.append(list(path)).
The loop runs i from start to the end. If i > start and nums[i] == nums[i - 1], the value was already tried at this level, so continue skips it.
Otherwise path.append(nums[i]) makes the choice, and backtrack(i + 1) explores every subset that extends this path with later indices.
path.pop() removes the choice. path is now exactly what it was before step 3, so the next i starts from a correct path.
Each subset has one increasing order of indices, and the skip test removes repeats among equal values. So each different subset is saved once.

Traps

i > 0 instead of i > start. The test then skips a value even when it is the first pick of its call. For [1, 1, 2], the result is [[], [1], [1, 2], [2]], and [1, 1] and [1, 1, 2] are missing.
No sort. The test compares only with the left neighbour. For [1, 2, 1], the two 1s are not neighbours, and [1] is saved twice.
Saving path and not list(path). The code saves one list object and keeps changing it with append and pop. For [1, 2, 2], the result is six empty lists.
Sorting when the order matters. Non-decreasing Subsequences (LC 491) asks for subsequences in the original order. Sorting creates subsequences that are not in the input. Keep the order and skip repeats with a used set that each call creates for itself.
Forgetting path.pop(). path keeps the old choice, and every later subset contains a wrong item.

Practice

Canonical LeetCode:Subsets II (LC 90)Non-decreasing Subsequences (LC 491)Combination Sum II (LC 40)Permutations II (LC 47)

Theory Context•Backtracking & State Search

Builds on Subsets, which you haven’t finished yet.

P2MediumBuilt on Subsets~4 min speedrun

Subsets with Duplicates (Sibling Deduplication)

Built on

SubsetsSort first, then skip a value that equals its left neighbour unless it is the first choice of its call, so no subset is saved twice.

The problem

Subsets II (LC 90)(opens leetcode.com)

Given an integer array nums that may hold duplicate values, produce the full power set -- every possible subset, including the empty subset and the full array itself.

Because nums can repeat values, two different index choices might describe the same subset of values; the returned list must not contain that subset twice. Return the subsets in any order.

Example 1

Input:nums = [1,2,2]

Output:[[],[1],[1,2],[1,2,2],[2],[2,2]]

Picking the first 2 or the second 2 gives the same subset, so [2] and [1,2] appear only once.

Subsets II

sorted elements ➔ skip an equal left neighbour ➔ each distinct subset once

Spot it when: You must list all subsets, and the input has repeated values, so the same subset must not be saved twice.

Subsets II

Python

1	from typing import List
2
3	def subsetsWithDup(nums: List[int]) -> List[List[int]]:
4	"""Subsets II (LC 90): every different subset of nums, saved once at the node of the decision tree that builds it.
5	Sort nums first, then skip nums[i] when i > start and nums[i] == nums[i - 1].
6	N = len(nums). The skip test costs O(1).
7	Time: O(N * 2^N) \| Space: O(N) path + recursion stack, output not counted
8	"""
9	nums.sort() # sort so equal values sit next to each other, needed for the skip test below
10	results: List[List[int]] = []
11	path: List[int] = [] # the choices from the root to the current node, in order
12
13	def backtrack(start: int) -> None:
14	# 1. Save This Node:
15	# Every node of the decision tree is a valid subset, so copy path into results
16	# as soon as the call starts, before trying any further choice.
17	results.append(list(path))
18
19	for i in range(start, len(nums)):
20	# 2. Skip a Repeated Sibling:
21	# nums is sorted, so two equal values sit next to each other; i > start means
22	# nums[i] is not the first choice tried at this level, so skip it to avoid
23	# building the same subset twice.
24	if i > start and nums[i] == nums[i - 1]:
25	continue
26
27	# 3. Choose, Explore, Un-choose:
28	# Add nums[i] to path, recurse forward so the next call only sees later
29	# indices, then remove nums[i] so the loop's next i tries its own branch.
30	path.append(nums[i])
31	backtrack(i + 1)
32	path.pop()
33
34	backtrack(0)
35	return results

Invariant: path always holds exactly the choices from the root to the current node, and no value is tried twice among the choices of one call, so every different subset is saved exactly once.

See it run

Subsets with duplicates, step by step

start 0path []saved 0

The top row is nums. The middle row is 1 when the item is in path. The bottom row is path, filled from the left.

i the index the loop is looking at
start the first index this call may use
i = start the loop index is the first index of this call
path the slot just added to path
undo the slot just removed from path

nums is sorted: [1, 2, 2]. path is empty, and backtrack(0) is about to run.

nums

1start

in path

path

1 / 20

Gotchas1 of 3

The trap
Gotcha 1: Writing i > 0 instead of i > start
Mistake
```
if i > 0 and nums[i] == nums[i - 1]:
```
Fix
```
if i > start and nums[i] == nums[i - 1]:
```
What happens: The skip test must skip a repeated value only among the choices of one call. With i > 0, the call backtrack(1) also skips the second 1. That call is the only way to put the second 1 after the first one. So [1, 1] and [1, 1, 2] are never built.
Example: nums = [1, 1, 2]
Mistake: returns [[], [1], [1, 2], [2]]Fix: returns [[], [1], [1, 1], [1, 1, 2], [1, 2], [2]]
Gotcha 2: Skipping duplicates without sorting nums first
Mistake
```
results: List[List[int]] = []
```
Fix
```
nums.sort()
results: List[List[int]] = []
```
What happens: The skip test compares nums[i] only with its left neighbour nums[i - 1]. Without the sort, two equal values can sit apart. The test then misses them, and the same subset is saved twice.
Example: nums = [2, 1, 2]
Mistake: returns [[], [2], [2, 1], [2, 1, 2], [2, 2], [1], [1, 2], [2]]Fix: returns [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
Gotcha 3: Sorting nums when the order of the values matters
Mistake
```
nums.sort()
```
Fix
```
used = set()  # values already tried in this call
if nums[i] in used:
    continue
used.add(nums[i])
```
What happens: Non-decreasing Subsequences (LC 491) asks for subsequences in the original order. Sorting nums creates subsequences that do not exist in the input. Keep the order, and skip a repeated value with a used set. Each call creates its own used set, so it only skips repeats among the choices of that call.
Example: Non-decreasing Subsequences (LC 491): nums = [3, 1]
Mistake: returns [[1, 3]]Fix: returns []

Not this one if…

All values are different, as in Subsets (LC 78), so no value can repeat a subset and no skip test is needed. See Subsets
The order matters and every element is used once, as in Permutations II (LC 47): the loop restarts at 0 and the skip test also needs the used array. See Permutations

Deep Dive

Skipping a repeated value: sort, then compare with the left neighbour

Take nums = [1, 2, 2]. The two 2s are different indices, so the plain tree builds [1, 2] twice and [2] twice. That is 8 nodes and 8 saved lists, and 2 of them are repeats.

With the test, [1, 2, 2] makes 6 calls and returns [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]. This is the example of Subsets II (LC 90).

The cost: nodes times the copy

For N = 20 different numbers, backtrack runs 1,048,576 times. The skip test costs O(1) after the sort, so it does not change this. The sort costs O(N log N) and is small next to 2^N.

Repeated values make the tree smaller, not larger. [1, 2, 2] has 6 nodes, not 8.

60-Second Pitch

Common Questions

Why do you save path at every call and not only when the index reaches the end?: Every path is already a valid subset, including the empty list at the first call. A save at the end would find only the subsets that use the last index. Saving at every node finds all of them, and each exactly once.
Why is the test i > start and not i > 0?: i > start skips a value only when an equal value was already the pick of this same call. i > 0 also skips the first pick of a call when the previous element is equal, and that pick is needed. For [1, 1, 2], i > 0 loses [1, 1] and [1, 1, 2].
What is the time and space complexity?: O(N * 2^N) time, because there are up to 2^N nodes and each one copies path in up to O(N). The space is O(N) for path and the recursion stack. The output is not counted. The sort adds O(N log N).
How does the answer change if the order inside a subset matters?: Then the problem is about orderings, not subsets. The loop restarts at 0 in every call and uses a used array, as in Permutations (LC 46). Subsets II (LC 90) and Permutations (LC 46) use the same choose, explore, undo structure and differ only in which indices the loop may try.
Why can you not sort the input for Non-decreasing Subsequences (LC 491)?: That problem asks for subsequences, which keep the original order. After sorting, a group such as [4, 6] can appear even when 6 comes before 4 in the input. Keep the order, and in each call skip a value that is already in a used set made for that call.

SWE Reasoning

Spot it

The statement asks for all subsets, all subsequences, or all on/off choices. The answer is a list of lists, not one number.
Every group is valid, including the empty group, so you save at every node and not only at a leaf.
The order inside a group does not matter. [1, 2] and [2, 1] count as one answer.
The input can hold equal values, and the answer must not list the same group twice. This is Subsets II (LC 90).
The input is small, usually 20 items or fewer, because the answer has up to 2^N groups.

The invariant, step by step

backtrack(start) is called with path holding the choices from the first call to this call. The first thing it does is results.append(list(path)).
The loop runs i from start to the end. If i > start and nums[i] == nums[i - 1], the value was already tried at this level, so continue skips it.
Otherwise path.append(nums[i]) makes the choice, and backtrack(i + 1) explores every subset that extends this path with later indices.
path.pop() removes the choice. path is now exactly what it was before step 3, so the next i starts from a correct path.
Each subset has one increasing order of indices, and the skip test removes repeats among equal values. So each different subset is saved once.

Traps

i > 0 instead of i > start. The test then skips a value even when it is the first pick of its call. For [1, 1, 2], the result is [[], [1], [1, 2], [2]], and [1, 1] and [1, 1, 2] are missing.
No sort. The test compares only with the left neighbour. For [1, 2, 1], the two 1s are not neighbours, and [1] is saved twice.
Saving path and not list(path). The code saves one list object and keeps changing it with append and pop. For [1, 2, 2], the result is six empty lists.
Sorting when the order matters. Non-decreasing Subsequences (LC 491) asks for subsequences in the original order. Sorting creates subsequences that are not in the input. Keep the order and skip repeats with a used set that each call creates for itself.
Forgetting path.pop(). path keeps the old choice, and every later subset contains a wrong item.

Practice

Canonical LeetCode:Subsets II (LC 90)Non-decreasing Subsequences (LC 491)Combination Sum II (LC 40)Permutations II (LC 47)

Theory Context•Backtracking & State Search

Builds on Subsets, which you haven’t finished yet.

P2MediumBuilt on Subsets~4 min speedrun

Subsets with Duplicates (Sibling Deduplication)

Built on

SubsetsSort first, then skip a value that equals its left neighbour unless it is the first choice of its call, so no subset is saved twice.

The problem

Subsets II (LC 90)(opens leetcode.com)

Given an integer array nums that may hold duplicate values, produce the full power set -- every possible subset, including the empty subset and the full array itself.

Because nums can repeat values, two different index choices might describe the same subset of values; the returned list must not contain that subset twice. Return the subsets in any order.

Example 1

Input:nums = [1,2,2]

Output:[[],[1],[1,2],[1,2,2],[2],[2,2]]

Picking the first 2 or the second 2 gives the same subset, so [2] and [1,2] appear only once.

Subsets II

sorted elements ➔ skip an equal left neighbour ➔ each distinct subset once

Spot it when: You must list all subsets, and the input has repeated values, so the same subset must not be saved twice.

Subsets II

Python

1	from typing import List
2
3	def subsetsWithDup(nums: List[int]) -> List[List[int]]:
4	"""Subsets II (LC 90): every different subset of nums, saved once at the node of the decision tree that builds it.
5	Sort nums first, then skip nums[i] when i > start and nums[i] == nums[i - 1].
6	N = len(nums). The skip test costs O(1).
7	Time: O(N * 2^N) \| Space: O(N) path + recursion stack, output not counted
8	"""
9	nums.sort() # sort so equal values sit next to each other, needed for the skip test below
10	results: List[List[int]] = []
11	path: List[int] = [] # the choices from the root to the current node, in order
12
13	def backtrack(start: int) -> None:
14	# 1. Save This Node:
15	# Every node of the decision tree is a valid subset, so copy path into results
16	# as soon as the call starts, before trying any further choice.
17	results.append(list(path))
18
19	for i in range(start, len(nums)):
20	# 2. Skip a Repeated Sibling:
21	# nums is sorted, so two equal values sit next to each other; i > start means
22	# nums[i] is not the first choice tried at this level, so skip it to avoid
23	# building the same subset twice.
24	if i > start and nums[i] == nums[i - 1]:
25	continue
26
27	# 3. Choose, Explore, Un-choose:
28	# Add nums[i] to path, recurse forward so the next call only sees later
29	# indices, then remove nums[i] so the loop's next i tries its own branch.
30	path.append(nums[i])
31	backtrack(i + 1)
32	path.pop()
33
34	backtrack(0)
35	return results

Invariant: path always holds exactly the choices from the root to the current node, and no value is tried twice among the choices of one call, so every different subset is saved exactly once.

See it run

Subsets with duplicates, step by step

start 0path []saved 0

The top row is nums. The middle row is 1 when the item is in path. The bottom row is path, filled from the left.

i the index the loop is looking at
start the first index this call may use
i = start the loop index is the first index of this call
path the slot just added to path
undo the slot just removed from path

nums is sorted: [1, 2, 2]. path is empty, and backtrack(0) is about to run.

nums

1start

in path

path

1 / 20

Gotchas1 of 3

The trap
Gotcha 1: Writing i > 0 instead of i > start
Mistake
```
if i > 0 and nums[i] == nums[i - 1]:
```
Fix
```
if i > start and nums[i] == nums[i - 1]:
```
What happens: The skip test must skip a repeated value only among the choices of one call. With i > 0, the call backtrack(1) also skips the second 1. That call is the only way to put the second 1 after the first one. So [1, 1] and [1, 1, 2] are never built.
Example: nums = [1, 1, 2]
Mistake: returns [[], [1], [1, 2], [2]]Fix: returns [[], [1], [1, 1], [1, 1, 2], [1, 2], [2]]
Gotcha 2: Skipping duplicates without sorting nums first
Mistake
```
results: List[List[int]] = []
```
Fix
```
nums.sort()
results: List[List[int]] = []
```
What happens: The skip test compares nums[i] only with its left neighbour nums[i - 1]. Without the sort, two equal values can sit apart. The test then misses them, and the same subset is saved twice.
Example: nums = [2, 1, 2]
Mistake: returns [[], [2], [2, 1], [2, 1, 2], [2, 2], [1], [1, 2], [2]]Fix: returns [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
Gotcha 3: Sorting nums when the order of the values matters
Mistake
```
nums.sort()
```
Fix
```
used = set()  # values already tried in this call
if nums[i] in used:
    continue
used.add(nums[i])
```
What happens: Non-decreasing Subsequences (LC 491) asks for subsequences in the original order. Sorting nums creates subsequences that do not exist in the input. Keep the order, and skip a repeated value with a used set. Each call creates its own used set, so it only skips repeats among the choices of that call.
Example: Non-decreasing Subsequences (LC 491): nums = [3, 1]
Mistake: returns [[1, 3]]Fix: returns []

Not this one if…

All values are different, as in Subsets (LC 78), so no value can repeat a subset and no skip test is needed. See Subsets
The order matters and every element is used once, as in Permutations II (LC 47): the loop restarts at 0 and the skip test also needs the used array. See Permutations

Deep Dive

Skipping a repeated value: sort, then compare with the left neighbour

Take nums = [1, 2, 2]. The two 2s are different indices, so the plain tree builds [1, 2] twice and [2] twice. That is 8 nodes and 8 saved lists, and 2 of them are repeats.

With the test, [1, 2, 2] makes 6 calls and returns [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]. This is the example of Subsets II (LC 90).

The cost: nodes times the copy

For N = 20 different numbers, backtrack runs 1,048,576 times. The skip test costs O(1) after the sort, so it does not change this. The sort costs O(N log N) and is small next to 2^N.

Repeated values make the tree smaller, not larger. [1, 2, 2] has 6 nodes, not 8.

60-Second Pitch

Common Questions

Why do you save path at every call and not only when the index reaches the end?: Every path is already a valid subset, including the empty list at the first call. A save at the end would find only the subsets that use the last index. Saving at every node finds all of them, and each exactly once.
Why is the test i > start and not i > 0?: i > start skips a value only when an equal value was already the pick of this same call. i > 0 also skips the first pick of a call when the previous element is equal, and that pick is needed. For [1, 1, 2], i > 0 loses [1, 1] and [1, 1, 2].
What is the time and space complexity?: O(N * 2^N) time, because there are up to 2^N nodes and each one copies path in up to O(N). The space is O(N) for path and the recursion stack. The output is not counted. The sort adds O(N log N).
How does the answer change if the order inside a subset matters?: Then the problem is about orderings, not subsets. The loop restarts at 0 in every call and uses a used array, as in Permutations (LC 46). Subsets II (LC 90) and Permutations (LC 46) use the same choose, explore, undo structure and differ only in which indices the loop may try.
Why can you not sort the input for Non-decreasing Subsequences (LC 491)?: That problem asks for subsequences, which keep the original order. After sorting, a group such as [4, 6] can appear even when 6 comes before 4 in the input. Keep the order, and in each call skip a value that is already in a used set made for that call.

SWE Reasoning

Spot it

The statement asks for all subsets, all subsequences, or all on/off choices. The answer is a list of lists, not one number.
Every group is valid, including the empty group, so you save at every node and not only at a leaf.
The order inside a group does not matter. [1, 2] and [2, 1] count as one answer.
The input can hold equal values, and the answer must not list the same group twice. This is Subsets II (LC 90).
The input is small, usually 20 items or fewer, because the answer has up to 2^N groups.

The invariant, step by step

backtrack(start) is called with path holding the choices from the first call to this call. The first thing it does is results.append(list(path)).
The loop runs i from start to the end. If i > start and nums[i] == nums[i - 1], the value was already tried at this level, so continue skips it.
Otherwise path.append(nums[i]) makes the choice, and backtrack(i + 1) explores every subset that extends this path with later indices.
path.pop() removes the choice. path is now exactly what it was before step 3, so the next i starts from a correct path.
Each subset has one increasing order of indices, and the skip test removes repeats among equal values. So each different subset is saved once.

Traps

i > 0 instead of i > start. The test then skips a value even when it is the first pick of its call. For [1, 1, 2], the result is [[], [1], [1, 2], [2]], and [1, 1] and [1, 1, 2] are missing.
No sort. The test compares only with the left neighbour. For [1, 2, 1], the two 1s are not neighbours, and [1] is saved twice.
Saving path and not list(path). The code saves one list object and keeps changing it with append and pop. For [1, 2, 2], the result is six empty lists.
Sorting when the order matters. Non-decreasing Subsequences (LC 491) asks for subsequences in the original order. Sorting creates subsequences that are not in the input. Keep the order and skip repeats with a used set that each call creates for itself.
Forgetting path.pop(). path keeps the old choice, and every later subset contains a wrong item.

Practice

Canonical LeetCode:Subsets II (LC 90)Non-decreasing Subsequences (LC 491)Combination Sum II (LC 40)Permutations II (LC 47)

Theory Context•Backtracking & State Search

Builds on Subsets, which you haven’t finished yet.

P2MediumBuilt on Subsets~4 min speedrun

Subsets with Duplicates (Sibling Deduplication)

Built on

SubsetsSort first, then skip a value that equals its left neighbour unless it is the first choice of its call, so no subset is saved twice.

The problem

Subsets II (LC 90)(opens leetcode.com)

Given an integer array nums that may hold duplicate values, produce the full power set -- every possible subset, including the empty subset and the full array itself.

Because nums can repeat values, two different index choices might describe the same subset of values; the returned list must not contain that subset twice. Return the subsets in any order.

Example 1

Input:nums = [1,2,2]

Output:[[],[1],[1,2],[1,2,2],[2],[2,2]]

Picking the first 2 or the second 2 gives the same subset, so [2] and [1,2] appear only once.

Subsets II

sorted elements ➔ skip an equal left neighbour ➔ each distinct subset once

Spot it when: You must list all subsets, and the input has repeated values, so the same subset must not be saved twice.

Subsets II

Python

1	from typing import List
2
3	def subsetsWithDup(nums: List[int]) -> List[List[int]]:
4	"""Subsets II (LC 90): every different subset of nums, saved once at the node of the decision tree that builds it.
5	Sort nums first, then skip nums[i] when i > start and nums[i] == nums[i - 1].
6	N = len(nums). The skip test costs O(1).
7	Time: O(N * 2^N) \| Space: O(N) path + recursion stack, output not counted
8	"""
9	nums.sort() # sort so equal values sit next to each other, needed for the skip test below
10	results: List[List[int]] = []
11	path: List[int] = [] # the choices from the root to the current node, in order
12
13	def backtrack(start: int) -> None:
14	# 1. Save This Node:
15	# Every node of the decision tree is a valid subset, so copy path into results
16	# as soon as the call starts, before trying any further choice.
17	results.append(list(path))
18
19	for i in range(start, len(nums)):
20	# 2. Skip a Repeated Sibling:
21	# nums is sorted, so two equal values sit next to each other; i > start means
22	# nums[i] is not the first choice tried at this level, so skip it to avoid
23	# building the same subset twice.
24	if i > start and nums[i] == nums[i - 1]:
25	continue
26
27	# 3. Choose, Explore, Un-choose:
28	# Add nums[i] to path, recurse forward so the next call only sees later
29	# indices, then remove nums[i] so the loop's next i tries its own branch.
30	path.append(nums[i])
31	backtrack(i + 1)
32	path.pop()
33
34	backtrack(0)
35	return results

Invariant: path always holds exactly the choices from the root to the current node, and no value is tried twice among the choices of one call, so every different subset is saved exactly once.

See it run

Subsets with duplicates, step by step

start 0path []saved 0

The top row is nums. The middle row is 1 when the item is in path. The bottom row is path, filled from the left.

i the index the loop is looking at
start the first index this call may use
i = start the loop index is the first index of this call
path the slot just added to path
undo the slot just removed from path

nums is sorted: [1, 2, 2]. path is empty, and backtrack(0) is about to run.

nums

1start

in path

path

1 / 20

Gotchas1 of 3

The trap
Gotcha 1: Writing i > 0 instead of i > start
Mistake
```
if i > 0 and nums[i] == nums[i - 1]:
```
Fix
```
if i > start and nums[i] == nums[i - 1]:
```
What happens: The skip test must skip a repeated value only among the choices of one call. With i > 0, the call backtrack(1) also skips the second 1. That call is the only way to put the second 1 after the first one. So [1, 1] and [1, 1, 2] are never built.
Example: nums = [1, 1, 2]
Mistake: returns [[], [1], [1, 2], [2]]Fix: returns [[], [1], [1, 1], [1, 1, 2], [1, 2], [2]]
Gotcha 2: Skipping duplicates without sorting nums first
Mistake
```
results: List[List[int]] = []
```
Fix
```
nums.sort()
results: List[List[int]] = []
```
What happens: The skip test compares nums[i] only with its left neighbour nums[i - 1]. Without the sort, two equal values can sit apart. The test then misses them, and the same subset is saved twice.
Example: nums = [2, 1, 2]
Mistake: returns [[], [2], [2, 1], [2, 1, 2], [2, 2], [1], [1, 2], [2]]Fix: returns [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
Gotcha 3: Sorting nums when the order of the values matters
Mistake
```
nums.sort()
```
Fix
```
used = set()  # values already tried in this call
if nums[i] in used:
    continue
used.add(nums[i])
```
What happens: Non-decreasing Subsequences (LC 491) asks for subsequences in the original order. Sorting nums creates subsequences that do not exist in the input. Keep the order, and skip a repeated value with a used set. Each call creates its own used set, so it only skips repeats among the choices of that call.
Example: Non-decreasing Subsequences (LC 491): nums = [3, 1]
Mistake: returns [[1, 3]]Fix: returns []

Not this one if…

All values are different, as in Subsets (LC 78), so no value can repeat a subset and no skip test is needed. See Subsets
The order matters and every element is used once, as in Permutations II (LC 47): the loop restarts at 0 and the skip test also needs the used array. See Permutations

Deep Dive

Skipping a repeated value: sort, then compare with the left neighbour

Take nums = [1, 2, 2]. The two 2s are different indices, so the plain tree builds [1, 2] twice and [2] twice. That is 8 nodes and 8 saved lists, and 2 of them are repeats.

With the test, [1, 2, 2] makes 6 calls and returns [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]. This is the example of Subsets II (LC 90).

The cost: nodes times the copy

For N = 20 different numbers, backtrack runs 1,048,576 times. The skip test costs O(1) after the sort, so it does not change this. The sort costs O(N log N) and is small next to 2^N.

Repeated values make the tree smaller, not larger. [1, 2, 2] has 6 nodes, not 8.

60-Second Pitch

Common Questions

Why do you save path at every call and not only when the index reaches the end?: Every path is already a valid subset, including the empty list at the first call. A save at the end would find only the subsets that use the last index. Saving at every node finds all of them, and each exactly once.
Why is the test i > start and not i > 0?: i > start skips a value only when an equal value was already the pick of this same call. i > 0 also skips the first pick of a call when the previous element is equal, and that pick is needed. For [1, 1, 2], i > 0 loses [1, 1] and [1, 1, 2].
What is the time and space complexity?: O(N * 2^N) time, because there are up to 2^N nodes and each one copies path in up to O(N). The space is O(N) for path and the recursion stack. The output is not counted. The sort adds O(N log N).
How does the answer change if the order inside a subset matters?: Then the problem is about orderings, not subsets. The loop restarts at 0 in every call and uses a used array, as in Permutations (LC 46). Subsets II (LC 90) and Permutations (LC 46) use the same choose, explore, undo structure and differ only in which indices the loop may try.
Why can you not sort the input for Non-decreasing Subsequences (LC 491)?: That problem asks for subsequences, which keep the original order. After sorting, a group such as [4, 6] can appear even when 6 comes before 4 in the input. Keep the order, and in each call skip a value that is already in a used set made for that call.

SWE Reasoning

Spot it

The statement asks for all subsets, all subsequences, or all on/off choices. The answer is a list of lists, not one number.
Every group is valid, including the empty group, so you save at every node and not only at a leaf.
The order inside a group does not matter. [1, 2] and [2, 1] count as one answer.
The input can hold equal values, and the answer must not list the same group twice. This is Subsets II (LC 90).
The input is small, usually 20 items or fewer, because the answer has up to 2^N groups.

The invariant, step by step

backtrack(start) is called with path holding the choices from the first call to this call. The first thing it does is results.append(list(path)).
The loop runs i from start to the end. If i > start and nums[i] == nums[i - 1], the value was already tried at this level, so continue skips it.
Otherwise path.append(nums[i]) makes the choice, and backtrack(i + 1) explores every subset that extends this path with later indices.
path.pop() removes the choice. path is now exactly what it was before step 3, so the next i starts from a correct path.
Each subset has one increasing order of indices, and the skip test removes repeats among equal values. So each different subset is saved once.

Traps

i > 0 instead of i > start. The test then skips a value even when it is the first pick of its call. For [1, 1, 2], the result is [[], [1], [1, 2], [2]], and [1, 1] and [1, 1, 2] are missing.
No sort. The test compares only with the left neighbour. For [1, 2, 1], the two 1s are not neighbours, and [1] is saved twice.
Saving path and not list(path). The code saves one list object and keeps changing it with append and pop. For [1, 2, 2], the result is six empty lists.
Sorting when the order matters. Non-decreasing Subsequences (LC 491) asks for subsequences in the original order. Sorting creates subsequences that are not in the input. Keep the order and skip repeats with a used set that each call creates for itself.
Forgetting path.pop(). path keeps the old choice, and every later subset contains a wrong item.

Practice

Canonical LeetCode:Subsets II (LC 90)Non-decreasing Subsequences (LC 491)Combination Sum II (LC 40)Permutations II (LC 47)