Permutations [Medium] — Backtracking via Swap

Problem Statement

Given an array of distinct integers, return all possible permutations.

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

Intuition

Swap the element at each position with every element to the right, recurse, then swap back (backtrack). Alternatively use a used boolean array.

Solutions

C++

void dfs(vector<int>& nums, int start, vector<vector<int>>& res) {
    if (start == nums.size()) { res.push_back(nums); return; }
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        dfs(nums, start + 1, res);
        swap(nums[start], nums[i]);
    }
}
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    dfs(nums, 0, res);
    return res;
}

Java

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    dfs(nums, 0, res);
    return res;
}
void dfs(int[] nums, int start, List<List<Integer>> res) {
    if (start == nums.length) {
        List<Integer> l = new ArrayList<>();
        for (int n : nums) l.add(n);
        res.add(l); return;
    }
    for (int i = start; i < nums.length; i++) {
        int t=nums[start]; nums[start]=nums[i]; nums[i]=t;
        dfs(nums, start+1, res);
        t=nums[start]; nums[start]=nums[i]; nums[i]=t;
    }
}

JavaScript

var permute = function(nums) {
    const res = [];
    function dfs(start) {
        if (start === nums.length) { res.push([...nums]); return; }
        for (let i = start; i < nums.length; i++) {
            [nums[start], nums[i]] = [nums[i], nums[start]];
            dfs(start + 1);
            [nums[start], nums[i]] = [nums[i], nums[start]];
        }
    }
    dfs(0);
    return res;
};

Python

def permute(nums: list[int]) -> list[list[int]]:
    res = []
    def dfs(start):
        if start == len(nums):
            res.append(nums[:])
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            dfs(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    dfs(0)
    return res

Complexity

Time: O(n! × n)
Space: O(n) recursion stack

Variant: Permutations II (with duplicates)

Sort first, then skip duplicate elements at the same recursion level using a used array.