Permutations

Generating all permutations means every ordering of the elements. Two common approaches: (1) build a path and mark which indices are used, or (2) swap elements in place and recurse on the remaining suffix.

When to Use

Problem asks for all permutations or all orderings.
Sometimes the problem is “next permutation” (single next in lex order), which is solved with a different algorithm (find pivot, swap, reverse).

Approach 1: Used Mask

Keep a path and a used[] array. At each step, try every index that is not yet used, add it to the path, mark used, recurse, then backtrack.

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

Time O(n!), space O(n).

Approach 2: Swap in Place

Permute the array in place: for index i, swap i with every j >= i, recurse on i+1, then swap back.

Java
void dfs(int[] nums, int i, List<List<Integer>> result) {
    if (i == nums.length) {
        result.add(Arrays.stream(nums).boxed().toList());
        return;
    }
    for (int j = i; j < nums.length; j++) {
        swap(nums, i, j);
        dfs(nums, i + 1, result);
        swap(nums, i, j);
    }
}

Same complexity; avoids an explicit used array.

Permutations with Duplicates

If the array has duplicates, you must avoid generating the same permutation multiple times. With the used-mask approach, skip adding nums[i] when nums[i] == nums[i-1] and !used[i-1] (so the first occurrence of that value at this level is used first).

Summary

Permutations: either try every unused index (with a used mask) or swap each position with every position to the right and recurse. Both yield O(n!) permutations. Handle duplicates by constraining which duplicate is used first.