全排列 II
Permutations II
题目详情
问题：全排列 II
考察：递归
来源：Citadel
链接：https://www.jointaro.com/interviews/questions/permutations-ii/
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]]
Example 2:
Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints:
1 <= nums.length <= 8-10 <= nums[i] <= 10
解析
思路：先排序，回溯时对重复数字做剪枝：同一层若前一个相同数字还没被使用，则跳过当前数字，避免重复排列。
复杂度：时间 O(n! * n) 上界，空间 O(n) 不计输出。