Duplicates in the input

One line, and understanding exactly why it is that line rather than a similar one.

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.

1def distinct_arrangements(items):2    results, current = [], []3    items = sorted(items)4    used = [False] * len(items)5 6    def explore():7        if len(current) == len(items):8            results.append(current[:])9            return10        for index in range(len(items)):11            if used[index]:12                continue13            if index > 0 and items[index] == items[index - 1] and not used[index - 1]:14                continue                # an equal earlier value is unplaced15            used[index] = True16            current.append(items[index])17            explore()18            current.pop()19            used[index] = False20 21    explore()22    return results23 24print(distinct_arrangements([1, 1, 2]))

Code lab· 30 min

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.

solution.py

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 tests to see output.

Problem· 25 min

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.

Problem· 25 min

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.

1def distinct_arrangements(items):2 results, current = [], []3 items = sorted(items)4 used = [False] * len(items)5 6 def explore():7 if len(current) == len(items):8 results.append(current[:])9 return10 for index in range(len(items)):11 if used[index]:12 continue13 if index > 0 and items[index] == items[index - 1] and not used[index - 1]:14 continue # an equal earlier value is unplaced15 used[index] = True16 current.append(items[index])17 explore()18 current.pop()19 used[index] = False20 21 explore()22 return results23 24print(distinct_arrangements([1, 1, 2]))