Permutations | Leetcode 46

Welcome to our deep dive on Permutations (Leetcode 46). This undeniably famous backtracking problem challenges you to methodically explore every potential combination of a dataset.

Problem Statement

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

Example: nums = [1,2,3] => Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Approach: Depth-First Search (Backtracking) O(N * N!)

Generating permutations requires exploring branching decision paths. At the first slot, we have $N$ choices. At the second slot, we have $N-1$ choices. Thus, the total number of permutations is $N!$ (N factorial).

To explicitly write these out mathematically in code, we use Backtracking (a specific form of DFS). We selectively append a number to our current path, dive deeper recursively to build the rest, and then—crucially—we "backtrack" by removing that number and trying the next available option!

1. Maintain an active path list and a visited boolean array (or just check if the element is already in the path).
2. Create a recursive dfs() function.
3. Base Case: If len(path) == len(nums), we successfully built a full permutation. Add a copy of it to the results list!
4. Recursive Step: Loop exactly through all elements in nums. If an element is not already in the current path:
   • Append it to the path (Make the choice).
   • Call dfs() recursively to build the next level.
   • Pop it from the path! (Undo the choice, i.e., "Backtrack").

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        
        def dfs(path):
            # Base Case: Our path has selected all numbers
            if len(path) == len(nums):
                res.append(path[:]) # Append a strict copy!
                return
                
            for num in nums:
                if num not in path:
                    # Choose
                    path.append(num)
                    # Explore
                    dfs(path)
                    # Backtrack
                    path.pop()
                    
        dfs([])
        return res

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (46)