全排列 II （Python）

LeetCode鏈接

時間復雜度 O(n * n!)
在全排列的基礎上加了個重復元素的情況，並且要求結果不能重復

思路：

1. 先對原始列表排序，使得重復元素都靠在一起
2. 之後在全排列的基礎上剪枝

class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res_list = []
path = []
nums_len = len(nums)
# 一個相同大小的標記數組 來標記某個下標是否被選擇過
selected = [False for _ in range(nums_len)]
def doit():
if len(path) == nums_len:
res_list.append(path[:])
return
for i in range(nums_len):
if not selected[i]:
# 因為已經對nums數組排過序了 此時nums[i] == nums[i - 1]表明可能是重復分支
# 但此時包含兩種情況 以 [1,1,2] 舉例
# 情況1、第一層選擇了 i=0處的1 第二層選擇了 i=1處的1 這種情況是正常的 不應當排除
# 情況2、第一層選擇了 i=1處的1 此時為重復分支 需要跳過
# 所以，僅僅判斷 nums[i] == nums[i - 1]仍然不夠
# 借助selected數組 
# 情況1 nums[i]雖然和num[i - 1]相等 但是selected[i - 1] is True表明nums[i - 1]是在上一層被選走的 此時num[i]可以被正常選擇
# 情況2 select[i - 1] is False 表明這就是個重復的情況 應當排除
if i > 0 and nums[i] == nums[i - 1] and not selected[i - 1]:
continue
# 標記選過
selected[i] = True
# 添加值
path.append(nums[i])
doit()
# 回滾
path.pop()
selected[i] = False
# 先排序保證重復元素靠在一起 這樣就可以看nums[i] 是否和nums[i - 1] 相等來判斷是否重復
nums.sort()
doit()
return res_list