0046.Permutations

Link: 46. Permutations - Medium
Track: NeetCode150

Question

Restate the problem

---

Method 1 - backtracking
Method 2

Method

Approach

(discussed at lease two approach?)

Complexity

• Time complexity: O($n!$)
• Space complexity: O($n!$)

Edge Case

Code

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        def dfs(path, used):
            
            if len(path) == n:
                res.append(path[:])
                return
 
            for num in nums:
                if num in used:
                    continue
                
                path.append(num)
                used.add(num)
                dfs(path, used)                
                path.pop()
                used.remove(num)
 
        dfs([], set())
        return res

---

History