5. Recursion

Backtracking intro

0 of 5 activities0%

Reading 1

Choose and revoke

Open

Backtracking builds a solution step by step. If a partial choice fails constraints, undo (pop) and try another.

Examples: permutations, N-queens, subset generation, mazes.

Template: choose → recurse → un-choose.

void dfs(vector<int>& path) {
  if (done) { save(); return; }
  for (choice) {
    path.push_back(choice);
    dfs(path);
    path.pop_back(); // undo
  }
}

Check 2

Undo

Open

The un-choose step usually

Fill in 3

Name

Open

Try it 4

Subsets of [1,2]

Open

Print all subsets sizes.

main.cpp

Loading editor…

Program input (stdin)

Output will appear here.

Assignment 5

Count subsets

Open

Read n. Print 2^n (number of subsets of an n-element set).

main.cpp

Loading editor…

Recursion patterns Linear search