46 Permutation

https://leetcode.com/problems/permutations/

solution

• 递归往下一层时，需要排除已经排过的元素，因此需要标记visited

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        path = []
        res = []
        used = [False] * len(nums)  # 非重复的，也可以用list/set 检查是否包含在list中，但如果有重复，这种记录位置的更好
        self.dfs(nums, path, res, used)
        return res

    def dfs(self, nums, path, res, used):
        if len(path) == len(nums):
            res.append(path[:])
            return

        for i in range(0, len(nums)):
            if used[i]:
                continue
            path.append(nums[i])
            used[i] = True
            self.dfs(nums, path, res, used)
            path.pop()
            used[i] = False

时间复杂度：O(n!) 空间复杂度：O(n)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []

        path = []
        res = []
        self.dfs(path, res, nums)
        return res

    def dfs(self, path, res, nums):
        if len(path) == len(nums):
            res.append(path.copy())

        for num in nums:
            if num not in path:
                path.append(num)
                self.dfs(path, res, nums)
                path.pop()

follow up

47. Permutations II

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        path = []
        res = []
        nums.sort()
        used = [False] * len(nums)
        self.dfs(nums, path, res, used)
        return res

    def dfs(self, nums, path, res, used):
        if len(path) == len(nums):
            res.append(path[:])
            return

        for i in range(0, len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i-1] and not used[i-1]:  # 注意这里的最后一个条件容易漏
                continue
            path.append(nums[i])
            used[i] = True
            self.dfs(nums, path, res, used)
            path.pop()
            used[i] = False

时间复杂度：O(n!) 空间复杂度：O(n)