templates · Backtracking

Backtracking: subsets

  • "Return all subsets" (the power set)
  • Every element is either in or out, and order inside a group does not matter
  • Small n (about 20 or less): 2ⁿ answers is fine

Backtracking: subsets

the one rule

The invariant

path holds the choices made on the way down; each call undoes its own choice, so path is the same before and after the call.

write it from memory

The template

all subsets

javajava.util.*
/** Every subset of nums (values distinct). */static List<List<Integer>> subsets(int[] nums) {    List<List<Integer>> out = new ArrayList<>();    collect(nums, 0, new ArrayList<>(), out);    return out;} private static void collect(int[] nums, int start, List<Integer> path, List<List<Integer>> out) {    out.add(new ArrayList<>(path));                   // every node of the tree is an answer: copy it    for (int i = start; i < nums.length; i++) {       // only look forward: no repeats in another order        path.add(nums[i]);                            // choose        collect(nums, i + 1, path, out);              // explore with what is left        path.remove(path.size() - 1);                 // un-choose    }}

Choose → explore → un-choose. Every call records path, because every node of this tree is a valid subset.

fill in the blanks — only these lines change per problem

  1. line 9When a path is an answer: always here; only at a certain size or sum in other problems.
  2. line 10Where the choices start. start stops the same subset from coming back in another order.
  3. line 11What one choice adds to the path.
  4. line 13The exact undo of the choose line.

with duplicate values

javajava.util.*
/** Every distinct subset when nums may hold equal values. */static List<List<Integer>> subsetsWithDup(int[] nums) {    int[] sorted = nums.clone();    Arrays.sort(sorted);                              // equal values now sit side by side    List<List<Integer>> out = new ArrayList<>();    collectUnique(sorted, 0, new ArrayList<>(), out);    return out;} private static void collectUnique(int[] nums, int start, List<Integer> path, List<List<Integer>> out) {    out.add(new ArrayList<>(path));    for (int i = start; i < nums.length; i++) {        if (i > start && nums[i] == nums[i - 1]) continue; // same value at the same level: skip        path.add(nums[i]);        collectUnique(nums, i + 1, path, out);        path.remove(path.size() - 1);    }}

Sort first. Then, at one level, use each value only once: i > start means "not the first choice at this level".

fill in the blanks — only these lines change per problem

  1. line 13The duplicate rule. It only works because the array is sorted.

complexity

What it costs

time O(n · 2ⁿ)
There are 2ⁿ subsets, and copying each one into the answer costs up to n.
space O(n) extra
The recursion depth and path are at most n. The answer itself holds n · 2ⁿ⁻¹ numbers, because each element sits in half of the subsets.

watch out

Common bugs

  • Adding path itself instead of new ArrayList<>(path). Every answer then points to the same list, which ends up empty.
  • Forgetting the un-choose line, so later answers keep old elements.
  • Skipping duplicates with i > 0 instead of i > start. That also removes valid answers like [2, 2].

use it

Practise it on

learn it properly