- Notifications
You must be signed in to change notification settings - Fork24
Open
Description
回溯
本题与46. 全排列解题思路一样。
不同之处：序列 nums 是可以重复的，要求按任意顺序返回所有不重复的全排列。
- 去重就要排序，排序后可以使相同的数字相邻，便于去重。
- 使用 used 数组记录使用过的数字，true 代表使用过，false 代表未使用过。
- 在迭代的过程中需要考虑好情况，充分剪枝。
- 在选择时记录
used[i]状态，撤销时也要重置used[i]状态。
constpermuteUnique=function(nums){constlen=nums.length,res=[],used=[]nums.sort((a,b)=>a-b)constbacktrack=(deepStack)=>{if(deepStack.length===len){res.push(deepStack.slice())return}for(leti=0;i<len;i++){// 当前选项与上一项相同、且上一项存在、且没有被使用过，则忽略if(nums[i-1]===nums[i]&&i-1>=0&&!used[i-1])continueif(used[i])continue// 使用过便不再使用deepStack.push(nums[i])used[i]=truebacktrack(deepStack)deepStack.pop()used[i]=false}}backtrack([])returnres}
- 时间复杂度: O(n * n!)
- 空间复杂度: O(n)
Metadata
Metadata
Assignees
Labels
No labels