46. Permutations

Difficulty: Medium

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

1. Backtracking

$O(n!)$ runtime,

$O(n)$ space

需要列出所有排列數，可以用backtracking。用take紀錄有沒有拿過nums的第i個元素。

python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        take = [False] * n
        
        result = []
        def backtracking(path):
            if len(path) == n:
                result.append(path)
                return
            
            for i in range(n):
                if not take[i]:
                    take[i] = True
                    backtracking(path + [nums[i]])
                    take[i] = False
        
        backtracking([])
        return result

用swap的方式，不需要額外的空間。

$O(n!)$ runtime,

$O(1)$ space

python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []

        def dfs(n_idx):
            if n_idx == n-1:
                res.append(nums[:])
                return
            
            for i in range(n_idx, n):
                nums[n_idx], nums[i] = nums[i], nums[n_idx]
                dfs(n_idx+1)
                nums[n_idx], nums[i] = nums[i], nums[n_idx]
            
        dfs(0)
        return res

tags: leetcode