LeetCode 47. Permutations II

用回溯法完成,跟普通排列问题不同的是,需要排除掉一些重复“路径”。

可以这样做,先把输入数组排个序,这样重复的数就在相邻位置了。随后在回溯探求的过程中,我们要保证相同值的两个数nums[i], nums[j],如果i<j,那遍历只能有一种次序:nums[i]先,nums[j]后。

换句话说,就是判断这种情况是需要提前终止的:两个数nums[i]==nums[j] && i<j,但是nums[i]还没有被遍历。所以找个东西记录一下访问就行了。

时间复杂度是O(N!),空间复杂度是O(N)

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注