Permutations — Practice

Problem

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

Examples

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]]

Explanation: All 3! = 6 orderings.

Constraints

•1 <= nums.length <= 6

Hints

Hint 1

Unlike Subsets, order matters here — [1,2] and [2,1] are different, distinct answers.

Hint 2

Track which elements are already 'used' in the current permutation-in-progress — the recursion considers every UNUSED element at each position, not a start index.

Hint 3

A result is only complete (added to the answer list) when the current permutation reaches the full length of nums — unlike Subsets, where every partial state was already valid.

Solutions

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

private void backtrack(int[] nums, List<Integer> current, boolean[] used, List<List<Integer>> result) {
    if (current.size() == nums.length) { // ONLY a complete permutation counts — unlike Subsets
        result.add(new ArrayList<>(current));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue; // skip elements already placed in this permutation
        used[i] = true;
        current.add(nums[i]);
        backtrack(nums, current, used, result);
        current.remove(current.size() - 1); // UNCHOOSE
        used[i] = false;                      // UNCHOOSE
    }
}

Time: O(n * n!) · Space: O(n) recursion depth, excluding output