全排列+回溯

一、46. 全排列 1.1、题目描述 1.2.1、回溯

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # visited 标注那个元素被访问过 
        visited = [False]*(len(nums))
        self._dfs(nums, [], visited)
        return self.res
    
    def __init__(self) -> None:
        self.res = []
        
    def _dfs(self, nums: List[int], tmpList: List[int], visited: List[int]) -> None:
        if len(tmpList) == len(nums):
            self.res.append(tmpList)
            return
        
        for i in range(len(nums)):
            if not visited[i]:
                visited[i] = True
                # tmpList + [nums[i]] 生成一个新的列表向下传递
                self._dfs(nums, tmpList + [nums[i]], visited)
                visited[i] = False  # 回溯
        

1.2.2、回溯

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self._dfs(nums, [], len(nums))
        return self.res
    
    def __init__(self) -> None:
        self.res = []
        
    def _dfs(self, nums: List[int], tmpList: List[int], vn: int) -> None:
        if len(tmpList) == vn:
            self.res.append(tmpList)
            return
        
        for i in range(len(nums)):
            # nums[:i, i+1:] 生成新的nums, 排除已经选择的元素
            self._dfs(nums[:i] + nums[i+1:], tmpList + [nums[i]], vn)
        

二、47. 全排列 II 思想

  当数组中有重复元素的时候，可以先将数组排序，排序以后在递归的过程中可以很容易发现重复的元素。当发现重复元素的时候，让这一个分支跳过，以达到“剪枝”的效果，重复的排列就不会出现在结果集中。

2.1、题目描述 2.2.1、回溯

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # visited 标注那个元素被访问过 
        visited = [False]*(len(nums))
        # 排序
        nums.sort()
        self._dfs(nums, [], visited)
        return self.res
    
    def __init__(self) -> None:
        self.res = []
        
    def _dfs(self, nums: List[int], tmpList: List[int], visited: List[int]) -> None:
        if len(tmpList) == len(nums):
            self.res.append(tmpList)
            return
        
        for i in range(len(nums)):
            # 剪枝， 前提需要nums排序
            if i > 0 and  nums[i] == nums[i-1] and visited[i-1]:
                continue
            
            if not visited[i]:
                visited[i] = True
                # tmpList + [nums[i]] 生成一个新的列表向下传递
                self._dfs(nums, tmpList + [nums[i]], visited)
                visited[i] = False  # 回溯
        

2.2.1、递归

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # 排序
        nums.sort()
        self._dfs(nums, [], len(nums))
        return self.res
    
    def __init__(self) -> None:
        self.res = []
        
    def _dfs(self, nums: List[int], tmpList: List[int], n: int) -> None:
        if len(tmpList) == n and tmpList not in self.res: # 剔除重复
            self.res.append(tmpList)
            return
        
        for i in range(len(nums)):
            self._dfs(nums[:i] + nums[i+1:], tmpList + [nums[i]], n)
        

三、31. 下一个排列 3.1、题目描述

3.2.1、峰谷值

1. 从后向前找一个谷底值a[i-1]
2. 从后向前找一个比谷底值大的最小值a[j],交换a[i-1], a[j]
3. 从i后逆序

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        
        # 从后往前找一个谷底
        i = n-2
        while i >= 0:
            if nums[i+1] > nums[i]:
                break
            i -= 1
        print(i)
        # 从谷底向后找，比起大的最小值
        if i >= 0:
            j = i+1
            while j = nums[j]:
                    break;
                j += 1
            j = j -1
            # 交换
            if j = 1:
            _sum *= i
            i -= 1
        return _sum


    def _dfs(self, nums: List[int], tmpList: str, n: int, k: int) -> str:
        if len(tmpList) == n:
            return tmpList   

        # 每层每个分支的数量
        _count =  self.__factorial(len(nums)-1)        
        
        for i in range(len(nums)):
        	# 剪枝， 小于k的分支不需要计算
            if k > _count:  # k大于分支排列数量
                k -= _count
            else:
                return self._dfs(nums[:i] + nums[i+1:], tmpList + str(nums[i]), n, k)