Lesson 13.2 · Backtracking

Subsets, Permutations and Combinations

A start index gives subsets and combinations (order doesn't matter); a used[] array gives permutations (order matters).

14 min

Think of it like this

Picking a cricket team versus setting a batting order. For the team, choosing Arjun then Priya is the same as Priya then Arjun, so you only look at players after the last one picked. For the batting order, position matters, so every unused player can go next.

1.Order doesn't matter: use start

Subsets and combinations only pick elements after the last one chosen (for i from start), so each set is generated once, in increasing index order. Combinations of size k record only when path.size() == k.

2.Order matters: use used[]

Permutations can pick any element not used yet, at every position. A boolean[] used marks what's in the path; set it on choose, clear it on unchoose. Record when the path is full. There are n! permutations.

Permutations.java

import java.util.*;

public class Main {
    static void permute(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> out) {
        if (path.size() == nums.length) { out.add(new ArrayList<>(path)); return; }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;  path.add(nums[i]);
            permute(nums, used, path, out);
            used[i] = false; path.remove(path.size() - 1);
        }
    }
    public static void main(String[] args) {
        List<List<Integer>> out = new ArrayList<>();
        permute(new int[]{1, 2, 3}, new boolean[3], new ArrayList<>(), out);
        System.out.println(out.size() + " " + out);
    }
}

Output

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

Quick check

How many results do subsets, k-combinations and permutations of n distinct elements produce?

Remember

start index → subsets/combinations.
used[] → permutations.
Results count: 2ⁿ, C(n, k), n!.

Common mistakes

Using start for permutations (misses orders).
Using used[] for subsets (generates duplicates in different orders).

Command Palette

Subsets, Permutations and Combinations

1.Order doesn't matter: use start

2.Order matters: use used[]