Course4all
Join us on telegram
Home/dsa/Backtracking/Permutations

Permutations

Master this topic with zero to advance depth.

Permutations

Exploration vs. Selection

In permutation problems, the goal is to arrange all elements of a set in every possible order. Unlike combinations, the order matters here ([1, 2] is different from [2, 1]).

Key Backtracking Strategies

  1. Visited Array: Maintain a boolean array to track which elements are already included in the current permutation. This is intuitive but uses extra space.
  2. Swap-Based: Swap the current element with every element to its right, recurse, and then swap back. This is highly efficient as it uses the input array for state.

Given an array nums of distinct integers, return all possible permutations. Includes visual state-space tree.

Medium

Examples

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

Level I: Backtracking with Visited Array

Intuition

Maintain a list of 'remaining' elements or a boolean array to track usage.

Iterate through all numbers. If a number is not visited, add it to the current permutation, mark it visited, and recurse. Unmark and remove after recursion.

⏱ O(N * N!)💾 O(N) for recursion stack and visited array.

Detailed Dry Run

Dry Run: nums=[1,2] | Path | Visited | Action | | :--- | :--- | :--- | | [] | {F, F} | Start | | [1] | {T, F} | Choose 1 | | [1,2] | {T, T} | Choose 2 (Result!) | | [1] | {T, F} | Backtrack | | [] | {F, F} | Backtrack | | [2] | {F, T} | Choose 2 | | [2,1] | {T, T} | Choose 1 (Result!) |
java
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(new ArrayList<>(), new boolean[nums.length], nums, res);
        return res;
    }
    private void backtrack(List<Integer> path, boolean[] used, int[] nums, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.add(nums[i]);
            backtrack(path, used, nums, res);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}
Approach 2

Level II: Backtracking with Swapping (In-Place)

Intuition

Instead of a visited array, we can rearrange the input array itself to represent the current state.

At index first, swap nums[first] with every element from first to N-1. Recurse for first + 1. This 'fixes' one element and permutes the rest.

⏱ O(N * N!)💾 O(N) for recursion stack.

Detailed Dry Run

nums=[1,2,3], first=0

  1. Swap(0,0): nums=[1,2,3]. Recurse first=1. 2. Swap(1,1): nums=[1,2,3]. Recurse first=2. SUCCESS [1,2,3]. 3. Swap(1,2): nums=[1,3,2]. Recurse first=2. SUCCESS [1,3,2].
  2. Swap(0,1): nums=[2,1,3]. Recurse first=1...
java
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        for (int n : nums) list.add(n);
        backtrack(0, list, res);
        return res;
    }
    private void backtrack(int first, List<Integer> nums, List<List<Integer>> res) {
        if (first == nums.size()) {
            res.add(new ArrayList<>(nums));
            return;
        }
        for (int i = first; i < nums.size(); i++) {
            Collections.swap(nums, first, i);
            backtrack(first + 1, nums, res);
            Collections.swap(nums, first, i); // Backtrack
        }
    }
}
Approach 3

Level III: Iterative Lexicographical Order

Intuition

Generate permutations in lexicographical order. This is useful when the input is sorted or we need to find the 'next' permutation.

Start with the smallest permutation (sorted). Repeatedly find the next lexicographical permutation until we return to the start.

⏱ O(N * N!)💾 O(1) extra space.

Detailed Dry Run

nums=[1,2,3]

  1. Initial: [1,2,3]
  2. Next: [1,3,2]
  3. Next: [2,1,3]
  4. Next: [2,3,1]
  5. Next: [3,1,2]
  6. Next: [3,2,1]
java
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        do {
            List<Integer> list = new ArrayList<>();
            for (int n : nums) list.add(n);
            res.add(list);
        } while (nextPermutation(nums));
        return res;
    }
    private boolean nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i+1]) i--;
        if (i < 0) return false;
        int j = nums.length - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums, i, j);
        reverse(nums, i + 1);
        return true;
    }
    private void swap(int[] nums, int i, int j) {
        int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
    }
    private void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) swap(nums, i++, j--);
    }
}
← Previous QuestionCombination Sum
Next Question →Subsets