Permutations

Problem

Given an array nums of distinct integers, return all the possible permutations. You can return the answer 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]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the integers of nums are unique.

Solution

I thought this was solvable with recursion, but it turns out it’s actually a backtracking problem.

Time complexity: O(n * n!)

Space complexity: O(n)

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        var answer = new ArrayList<List<Integer>>();
        permute(nums, List.of(), answer);
        return answer;
    }

    public void permute(int[] nums, List<Integer> curr, List<List<Integer>> answer) {
        if (curr.size() == nums.length) {
            answer.add(curr);
        }

        for (var n : nums) {
            if (curr.contains(n)) {
                continue;
            }
            var l = new ArrayList<>(curr);
            l.add(n);
            permute(nums, l, answer);
        }
    }
}

Recent posts from blogs that I like

An Introduction to Google’s Approach to AI Agent Security

via Simon Willison

Notes on Cramer's rule

Cramer's rule is a clever solution to the classical system of linear equations Ax=b: \[\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix} \begin{bmatrix}x_1 \\ x_2 \\ x_3\end{bmatrix} = \begin{bmatrix}b_1 \\ b_2 \\ b_3\end{bmatrix}\] Usi...

via Eli Bendersky

Brandjes: Paintings as witnesses to fires 1640-1813

Dramatic paintings of towns and cities on fire, usually at night, were popular during the Dutch Golden Age, and known as brandjes. Examples to well into the 19th century.

via The Eclectic Light Company