https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/

python
展开代码
from typing import List
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(start):
            if start == n:
                sol.append(nums[:])
            for i in range(start, n):
                nums[start], nums[i] =  nums[i], nums[start]
                dfs( start+1 )
                nums[start], nums[i] =  nums[i], nums[start]
        sol = []
        n = len(nums)
        dfs(0)
        return sol
a = Solution()
print(a.permute([1, 2, 3]))

或者写成：

展开代码
from typing import List
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(sol):
            if len(sol) == n:
                res.append(nums[:])
            for i in range(0, n):
                if used[i]: continue
                sol.append(nums[i])
                used[i] = 1
                dfs(sol)
                sol.pop()
                used[i] = 0
        res = []
        n = len(nums)
        used = [0 for _ in range(n)]
        dfs([])
        return res
print(Solution().permute([1, 2, 3]))

https://leetcode-cn.com/problems/permutations-ii/solution/

python
展开代码
from typing import List
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs(sol):
            if len(sol) == n:
                res.append(sol[:])
                return
            for i in range(0, n):  # nums 不改变
                # print(i, used)
                if used[i]: continue  # 当前位置的元素被使用过
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue  # 剪枝：新位置元素和上一个相同，并且上一个元素是没用过
                sol.append(nums[i])
                used[i] = 1
                dfs(sol)
                sol.pop()
                used[i] = 0
        res = []
        n = len(nums)
        nums.sort()
        used = [0 for i in range(n)]  # 全局，看看是第几层递归
        dfs([])
        # res=[tuple(i) for i in res]
        # return list(set(res))
        return res
print(Solution().permuteUnique([1, 1, 1]))