604. Every Distinct Ordering
A toy shop arranges coloured blocks in a row. The array nums gives the colour code of each block; several blocks may share a colour, and blocks of the same colour look identical.
Return every different row that can be built using all the blocks. Two rows are the same if they show the same colour at every position. Each different row must appear exactly once in the answer. The rows may be returned in any order, but the order of colours inside a row matters.
Example 1
- Input:
- nums = [1,1,0]
- Output:
- [[0,1,1],[1,0,1],[1,1,0]]
- Explanation:
Only three rows exist:
[0, 1, 1],[1, 0, 1]and[1, 1, 0].
Example 2
- Input:
- nums = [2,2,2]
- Output:
- [[2,2,2]]
- Explanation:
All blocks look the same, so there is a single row.
Example 3
- Input:
- nums = [0,1,2]
- Output:
- [[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]]
- Explanation:
Three different colours give 3! = 6 rows.
Constraints
- 1 ≤
nums.length≤ 7 - 0 ≤
nums[i]≤ 2
With these limits the answer has at most 210 rows.
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
Expected complexity
- Time
- O(n * n!)
- Space
- O(n)