1775. Nobody Gets Their Own
At an office gift swap, n colleagues are numbered 1 to n, and each one brings a present labelled with the same number. The gifts are handed out so that every person receives exactly one present, and nobody may receive the present they brought. Describe an assignment as an array in which position p (1-based) holds the label of the present given to person p.
Return all such assignments, that is, all permutations of 1..n where no value sits at its own 1-based position. List them in lexicographic order. When there is none (for example n = 1), return an empty list. Use backtracking with a bitmask of used values, trying values in ascending order and skipping value p at position p. For n = 6 there are 265 rows, so the work is proportional to the output, O(n * D(n)) time, with O(n) extra space.
Example 1
- Input:
- n = 2
- Output:
- [[2,1]]
- Explanation:
Only swapping the two people works.
Example 2
- Input:
- n = 3
- Output:
- [[2,3,1],[3,1,2]]
- Explanation:
The two 3-cycles are the only assignments where nobody keeps their own gift.
Constraints
1 ≤ n ≤ 6 (at most 265 rows; n = 1 gives an empty list)
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n * D(n))
- Space
- O(n)