Permutations

NeetCode: Permutations · LeetCode: 46. Permutations · Difficulty: Medium

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

Example

Text

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

Brute force: pick any unused element with a used array

Build a permutation position by position. At each position try every element that has not been used yet, marking it in a boolean[] used array and unmarking it after the recursive call. When the permutation has n elements, save a copy of it. Every branch leads to a valid permutation, so no work is wasted; the cost is the extra used array and a scan of all n slots at every level.

LeetCode's Java signature returns List<List<Integer>>. The current list is shared by every call, so a leaf stores new ArrayList<>(current), a copy; storing current itself would leave the result holding the same list many times. main sorts the permutations with a small comparator helper before printing, so the output does not depend on generation order.

Java

import java.util.ArrayList;
import java.util.List;

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

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

    static int cmp(List<Integer> a, List<Integer> b) {
        for (int i = 0; i < Math.min(a.size(), b.size()); i++) {
            int x = a.get(i), y = b.get(i);
            if (x != y) {
                return Integer.compare(x, y);
            }
        }
        return Integer.compare(a.size(), b.size());
    }

    static List<List<Integer>> sorted(List<List<Integer>> lists) {
        List<List<Integer>> copy = new ArrayList<>(lists);
        copy.sort(Main::cmp);
        return copy;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(sorted(s.permute(new int[] {1, 2, 3})));
        System.out.println(s.permute(new int[] {1}));
    }
}

Output

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

current.remove(current.size() - 1) removes by index because the argument is an int. List<Integer>.remove(Integer.valueOf(x)) would remove by value instead.

Time: O(n · n!). Space: O(n) besides the output.

Optimal: swap elements in place

Both versions are optimal, because the output alone has n! permutations of length n. The swap version needs less bookkeeping. Keep the array split in two: nums[0..i) is the prefix already fixed and nums[i..n) holds the elements still available. To fix position i, swap each candidate nums[j] (for j >= i) into it, recurse on i + 1, then swap back to restore the array. No used array and no separate current list are needed. A leaf copies the array into a List<Integer>.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class Solution {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
            dfs(0, nums, result);
            return result;
        }

        private void dfs(int i, int[] nums, List<List<Integer>> result) {
            if (i == nums.length) {
                List<Integer> copy = new ArrayList<>();
                for (int x : nums) {
                    copy.add(x);
                }
                result.add(copy);
                return;
            }
            for (int j = i; j < nums.length; j++) {
                swap(nums, i, j);
                dfs(i + 1, nums, result);
                swap(nums, i, j); // undo
            }
        }

        private void swap(int[] nums, int a, int b) {
            int t = nums[a];
            nums[a] = nums[b];
            nums[b] = t;
        }
    }

    static int cmp(List<Integer> a, List<Integer> b) {
        for (int i = 0; i < Math.min(a.size(), b.size()); i++) {
            int x = a.get(i), y = b.get(i);
            if (x != y) {
                return Integer.compare(x, y);
            }
        }
        return Integer.compare(a.size(), b.size());
    }

    static List<List<Integer>> sorted(List<List<Integer>> lists) {
        List<List<Integer>> copy = new ArrayList<>(lists);
        copy.sort(Main::cmp);
        return copy;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(sorted(s.permute(new int[] {1, 2, 3})));
        System.out.println(s.permute(new int[] {1}));
    }
}

Output

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

Time: O(n · n!). Space: O(n) recursion depth besides the output. The method swaps inside the caller's array and restores it before returning. The permutations come out in a different order than in the first version, so main sorts them before printing.