Permutations

Problem

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

Solution

Approach: Backtracking with Visited Set

The key insight is to build permutations by trying each unused element at each position, using a set to track which elements are used.

Implementation

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

        def backtrack(path):
            if len(path) == len(nums):
                result.append(path[:])
                return

            for num in nums:
                if num not in path:
                    path.append(num)
                    backtrack(path)
                    path.pop()

        backtrack([])
        return result

Using Visited Set:

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

        def backtrack(path, used):
            if len(path) == len(nums):
                result.append(path[:])
                return

            for i, num in enumerate(nums):
                if i not in used:
                    path.append(num)
                    used.add(i)
                    backtrack(path, used)
                    used.remove(i)
                    path.pop()

        backtrack([], set())
        return result

Complexity Analysis

Time Complexity: O(n! * n), where n is the length of nums. There are n! permutations and each takes O(n) to copy.
Space Complexity: O(n) for recursion depth and path.

Key Insights

Factorial Permutations: For n distinct elements, there are n! permutations (n choices for first position, n-1 for second, etc.).
Try Every Element: Unlike subsets or combinations, we try every unused element at each position.
Visited Tracking: We need to track which elements are already in the current path to avoid duplicates within a permutation.
Path Length: Base case is when path length equals input length - we have a complete permutation.
Order Matters: Unlike combinations, [1,2,3] and [3,2,1] are different permutations.