【代码随想录】回溯4-排列

46.全排列

link

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

思路

• 参数和返回值：排序是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，所以处理排列问题就不用使用startIndex了。但排列问题需要一个used数组，标记已经选择的元素，如图橘黄色部分所示。

• 终止条件：cur 长度等于 nums 长度

• 单层逻辑：每次都需要从头开始选取，不能从 start 开始。此时使用 used 数组来标识当前元素是否被使用过。
  

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        cur = []
        res = []
        used = [False] * len(nums)

        def backtrack():
            if len(cur) == len(nums):
                res.append(cur[:])
                return 
            
            for i in range(len(nums)):
                if used[i]:
                    continue
                
                cur.append(nums[i])
                used[i] = True
                backtrack()
                cur.pop()
                used[i] = False
        backtrack()
        return res

47.全排列 II

link

去重逻辑类似于 子集II，首先将数组排序，如果当前数字和上一个数字相同并且当前层已经使用过，就跳过

used[i - 1] == true，说明同一树枝 candidates[i - 1]使用过
used[i - 1] == false，说明同一树层 candidates[i - 1]使用过
而我们要对同一树层使用过的元素进行跳过

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        cur = []
        res = []
        used = [False] * len(nums)
        nums.sort()
        def backtrack():
            if len(cur) == len(nums):
                res.append(cur[:])
                return 
            
            for i in range(len(nums)):
                if used[i]:
                    continue
                if i != 0 and nums[i] == nums[i-1] and used[i-1] == False:
                    continue
                cur.append(nums[i])
                used[i] = True
                backtrack()
                cur.pop()
                used[i] = False
        backtrack()
        return res