Backtracking
Duplicates in the input
One line, and understanding exactly why it is that line rather than a similar one.
Key idea
Where the duplicates come from
When the input contains equal values, two different branches can produce identical results. Choosing the first 2 and then continuing gives the same thing as choosing the second 2 and then continuing.
The fix is not to filter results afterward. It is to make sure that among a group of equal values, only the first one is ever chosen at a given level.
Why it works
Sort, then skip equal siblings
Sort the input so equal values are adjacent. Then inside the loop, skip any value equal to the one just before it at the same level.
The condition is index > start and items[index] == items[index - 1]. Every part of that matters and the next section takes it apart.
Key idea
Why `index > start` and not `index > 0`
For a combination search the guard is index > start. The comparison is against the loop's own starting point, not against zero.
The reason: at the top of each level, start is the first index this level may choose from. Two equal values are only siblings, meaning alternatives to each other at the same level, when both are at or after start. An equal value earlier than start sits on the path above, where it was chosen rather than being an alternative.
Writing index > 0 would also skip the second of a pair whose first was chosen by an ancestor, which wrongly forbids using both copies in one result.
Tip
The permutation version is different
In the arrangement search above there is no start index, so the guard compares against the used markers instead: skip a value equal to the previous one when that previous one is not currently placed.
The reasoning is the same. If the earlier equal value is unplaced, then choosing this one now would duplicate a branch where the earlier one was chosen instead. If the earlier one is placed, this is a legitimate second copy.
Two different guards for two different search shapes, both enforcing the same rule: among equal values, use them in order.
Gotcha
The sort is not optional
Both guards compare against the immediately previous element and therefore assume equal values are adjacent. Without the sort, duplicates spread through the list are never adjacent and the guard silently does nothing.
If a deduplicating search returns duplicates anyway, the missing sort is the first thing to check.
Tip
The honest alternative
Collecting everything and putting it in a set does work, when the results are hashable. It costs the full unpruned search plus the memory to hold every duplicate.
Say it as the fallback and then give the skip rule. Being able to explain why the skip works is what the question is testing; the set is what you would do if you had forgotten.
Deduplicating drills
Write both guard styles. distinct_combinations lists every distinct combination of the given size from a list that may contain repeats. distinct_arrangements lists every distinct ordering of a list that may contain repeats. Sort first in both.
Tests
print(distinct_combinations([1, 2, 2], 2)) print(distinct_combinations([1, 1, 1], 2)) print(distinct_arrangements([1, 1, 2])) print(distinct_arrangements([]))
Output
Run the tests when you are ready.
Subsets Ii
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Combination Sum Ii
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.