Leetcode 46. Permutations

Problem

Leetcode 46 - Permutations

Example:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Input: nums = [1]
Output: [[1]]

Approach

We can use DFS to backtrack. Since we need to find the permutation for unique element, we can use visited array to track the visited elements.

Here is the Python code for the solution:

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        visited = [False] * len(nums)

        def dfs(arr):
            if len(arr) == len(nums):
                if arr in res:
                    return
                res.append(arr.copy())
                return
            
            for i in range(len(nums)):
                if visited[i] == True:
                    continue
                
                visited[i] = True
                arr.append(nums[i])
                dfs(arr)
                visited[i] = False
                arr.pop()
        
        dfs([])
        return res    

Time Complexity and Space Complexity

Time Complexity: $O(N * N!)$

Space Complexity: $O(n)$