Permutations

medium backtracking permutations

Problem

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

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;
}

Explanation

We want every possible ordering of the array. This solution does it with a clean swap-and-recurse trick that rearranges the array in place instead of building a separate list.

Think of a pointer i that marks the slot we are currently deciding. For that slot we try putting each remaining element there: for every j from i to the end we swap a[i] and a[j], recurse with i + 1 to fill the next slot, then swap back to restore the array before trying the next choice.

The swap-back is the backtracking step — it undoes our change so each branch starts from the same clean state.

When i reaches the end of the array, every slot has been fixed, so the current array is one complete permutation and we copy it into the result.

Example: nums = [1, 2, 3]. At slot 0 we keep 1 and permute [2,3], then swap to put 2 first, then 3 first. Each choice fans out into the smaller sub-permutations, giving all 3! = 6 orderings.

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