All Permutations of an Array

medium backtracking permutations

Problem

Given an array of distinct integers, return every possible ordering — n! of them.

Recurse with a slot index i starting at 0. For each j in i..n-1, swap a[i] with a[j], recurse with i + 1, then swap back. When i == n, the array is a fresh permutation — copy it into the result.

Inputnums = [1, 2, 3]

Output[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,2,1] [3,1,2]

Six orderings = 3!. Order depends on the swap traversal.

nums (distinct, comma-separated)

def permute(nums):
    out = []
    def back(i):
        if i == len(nums):
            out.append(nums.copy()); return
        for j in range(i, len(nums)):
            nums[i], nums[j] = nums[j], nums[i]
            back(i + 1)
            nums[i], nums[j] = nums[j], nums[i]
    back(0)
    return out

function permute(nums) {
  const out = [];
  function back(i) {
    if (i === nums.length) { out.push(nums.slice()); return; }
    for (let j = i; j < nums.length; j++) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      back(i + 1);
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  }
  back(0);
  return out;
}

List<List<Integer>> out = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
    back(nums, 0);
    return out;
}
void back(int[] a, int i) {
    if (i == a.length) {
        List<Integer> row = new ArrayList<>();
        for (int x : a) row.add(x);
        out.add(row); return;
    }
    for (int j = i; j < a.length; j++) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
        back(a, i + 1);
        t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

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

Time: O(n · n!) Space: O(n) recursion