46. Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        seen = set()
        acc = []
        ans = []
        
        def backtrack():
            if len(acc) == len(nums):
                ans.append(acc[:])
            else:
                for num in nums:
                    if num not in seen:
                        seen.add(num)
                        acc.append(num)
                        
                        backtrack()
                        
                        acc.pop()
                        seen.remove(num)
        
        backtrack()
        return ans

• classic backtracking.
• don’t actually have to pass accumulator and seen sets in the function call. We can just add to it before we call backtrack() and reset it after returning from the call.

Categories:: array, backtracking