Every Possible Ordering of a Set of Distinct Numbers

Medium20–25 min

Topics

BacktrackingRecursionArray

Companies

AmazonMicrosoftAdobe

Given an array of distinct integers, produce every possible ordering of its elements. Unlike a subset or combination, order matters here — [5, 7, 9] and [7, 5, 9] are two different, equally valid answers. A path can be extended with any element not already placed in it; tracking "already placed" as an explicit list that gets filtered down at every node works, but rebuilds and copies that list at every single step. Swapping that out for one fixed-size array of used-flags removes the rebuilding entirely — checking or flipping a flag never depends on how many elements are left, only on marking and unmarking a single index as the recursion goes in and comes back out.

Test Case 1:

Input:nums = [5, 7, 9]

Output:[[5, 7, 9], [5, 9, 7], [7, 5, 9], [7, 9, 5], [9, 5, 7], [9, 7, 5]]

Explanation:3 elements produce 3! = 6 orderings, listed in ascending order.

Test Case 2:

Input:nums = [2, 4]

Output:[[2, 4], [4, 2]]

Explanation:Only two possible orderings for two elements.

Test Case 3:

Input:nums = [8]

Output:[[8]]

Explanation:A single element has exactly one arrangement: itself.

Constraints

◆1 ≤ nums.length ≤ 7
◆-20 ≤ nums[i] ≤ 20, and every value in nums is distinct
◆Results are returned sorted in ascending (lexicographic) order for a stable, checkable answer

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Rebuild the Remaining Elements at Every Step

Brute

Track which elements are still available as an explicit list rather than a fixed-size flag array. At each node, try every element still in that list: remove it to build a brand-new "remaining" list for the recursive call, append it to the path, recurse, then pop it back off the path afterward. Correct, but a fresh remaining-list is allocated and copied at every single node — O(n) wasted work per node on top of the n! · n work that's unavoidable just to write out every permutation.

TimeO(n! · n²)

SpaceO(n! · n)

Java

Try it out

class Solution {
    public int[][] allPermutationsOf(int[] nums) {
        List<int[]> result = new ArrayList<>();
        List<Integer> remaining = new ArrayList<>();
        for (int v : nums) remaining.add(v);
        generate(remaining, new ArrayList<>(), result);
        result.sort((a, b) -> {
            for (int i = 0; i < a.length; i++) {
                if (a[i] != b[i]) return a[i] - b[i];
            }
            return 0;
        });
        return result.toArray(new int[0][]);
    }

    private void generate(List<Integer> remaining, List<Integer> path, List<int[]> result) {
        if (remaining.isEmpty()) {
            int[] row = new int[path.size()];
            for (int j = 0; j < row.length; j++) row[j] = path.get(j);
            result.add(row);
            return;
        }
        for (int i = 0; i < remaining.size(); i++) {
            List<Integer> nextRemaining = new ArrayList<>(remaining);
            nextRemaining.remove(i);
            path.add(remaining.get(i));
            generate(nextRemaining, path, result);
            path.remove(path.size() - 1);
        }
    }
}

Optimal — Shared Path With a Used-Flags Array

Optimal

Keep one fixed-size boolean array marking which positions of nums are already in the current path, instead of rebuilding a filtered list every time. At each node, scan the flags and try every not-yet-used index: mark it used, append it to a single shared path array, recurse, then unmark it and pop it back off. No list is ever allocated or copied — checking and flipping a flag is O(1), so the only work done is exactly what's needed to write out each permutation.

TimeO(n! · n)

SpaceO(n)