Command Palette

Search for a command to run...

Hectal
Problem 13.3 · BacktrackingMedium

Permutations

PatternBacktracking

What it teaches: When order matters, any unused element can go next: track usage with a boolean array.

Practise it on judges as “Permutations”.

The problem

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

Example 1

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

Constraints

  • 1 ≤ nums.length ≤ 6
  • Distinct

Pattern clues in the wording

  • → "All orderings"
  • → n ≤ 6: n! = 720

These clues point to Backtracking: Build a candidate one choice at a time; when a choice can't lead to an answer, undo it and try the next.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

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

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
2
nums = [0,1]
[[0,1],[1,0]]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Backtracking with used[] · O(n · n!)
1

Backtracking with used[]

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

For each position, loop over all elements, skipping used ones; mark, recurse, unmark.

Approach 1
import java.util.*;

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

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

Verdict: Standard.

Before you submit

Edge cases and common mistakes

Test these inputs

  • One element

Mistakes people make

  • Forgetting to clear used[i] on the way back.

Interview

Follow-up questions

What if the input has duplicates?