[LeetCode] 46. Permutations

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

Use backtracking approach to find all combinations.

Let permutation[i] = permutation starts with nums[i],

nums[] - nums[i] = nums without nums[i]

permutation[i] = nums[i] + permutation( nums[] - nums[i] )

Time Complexity = O(n * n!)

Space Complexity = O(n * n!)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        
        if not nums: return []
        
        N = len(nums)
        result = []
        
        def swap(i, j):
            nums[i], nums[j] = nums[j], nums[i]
        
        def backtrack(start):
            if start == N:
                result.append(nums[:])
            else:
                for i in range(start, N):
                    swap(i, start)
                    backtrack(start+1)
                    swap(i, start)
        
        backtrack(0)
        return result