Permutations

Problem

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

Constraints

• 1 ≤ nums.length ≤ 6
• all distinct

Approach — Backtracking

This is a Backtracking problem. The idea: build candidates one choice at a time and abandon a branch the moment it can't lead to a valid answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: exponential worst case.

Solution code

Python

class Solution:
    def permute(self, nums):
        res = []
        def bt(cur, rem):
            if not rem:
                res.append(cur); return
            for i in range(len(rem)):
                bt(cur + [rem[i]], rem[:i] + rem[i+1:])
        bt([], nums)
        return res

Java

import java.util.*;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> out = new ArrayList<>();
        bt(out, new ArrayList<>(), nums, new boolean[nums.length]);
        return out;
    }

    private void bt(List<List<Integer>> out, List<Integer> cur, int[] nums, boolean[] used) {
        if (cur.size() == nums.length) { out.add(new ArrayList<>(cur)); return; }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            cur.add(nums[i]);
            bt(out, cur, nums, used);
            cur.remove(cur.size() - 1);
            used[i] = false;
        }
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.