How do you generate all permutations of an array?

Question presented to candidate: "Given a list of distinct integers, return all of its permutations. Write it in Python with backtracking, and then tell me how you would handle duplicate values."

What a strong answer should cover:

• There are n! permutations of n distinct elements: n choices for the first position, n - 1 for the second, and so on.
• Backtracking with a used marker: pick any unused element for the next position, recurse, then undo both the path and the marker.
• The in-place swap alternative (fix position k by swapping each candidate into it) and how its output order differs.
• Complexity O(n · n!) time, O(n) extra space; impossible to beat when all permutations must be listed.
• Duplicates (Permutations II): sort, and skip nums[i] when it equals nums[i - 1] and nums[i - 1] is not used; or the next-permutation algorithm.
• Python details: copy with path[:], the tuple swap a[k], a[i] = a[i], a[k], and itertools.permutations as the library version — which treats equal values as different, so it repeats permutations of [1, 1, 2].

Clarifying questions expected:

• Are the values distinct, and if not, should equal permutations appear once?
• Does the output need to be in sorted (lexicographic) order?
• Do you need all of them, or just the next one / the k-th one?

Code / implementation expected: Yes — a backtracking function in Python with a used list (or in-place swaps), plus the duplicate-skip rule.