Distinct Bead Strings
MediumBacktracking
Problem
You thread beads onto a string. Each bead has a colour code from nums; several beads may share a colour and are then indistinguishable.
Return every distinct sequence of colours you can produce using all the beads exactly once. Return the sequences in any order.
Example 1
- Input:
- nums = [1, 1, 2]
- Output:
- [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
3! = 6 orderings of positions, but swapping the two 1-beads changes nothing, so only 3 are distinct.
Example 2
- Input:
- nums = [3, 1, 2]
- Output:
- all 6 orderings of 1, 2, 3
Constraints
- 1 ≤ nums.length ≤ 8
- -10 ≤ nums[i] ≤ 10
Hint
Show the first hint
Start from the ordinary permutation recursion with a used[] array. Where do duplicates appear?
Walkthrough
How to approach it
01Clarify before coding
- Are beads of the same colour interchangeable? Yes, so [1a, 1b, 2] and [1b, 1a, 2] are one answer.
- Must every bead be used? Yes, each sequence has length n.
- Output order? Any.
02Brute force
Generate all n! permutations of positions and deduplicate them with a set of tuples.
Cost: O(n · n!) time and memory for the set; with 8 identical beads you build 40,320 sequences to keep 1.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.