These are the notes for C++ Coding Questions, episode 21, placement practice for people who finished the SyntaxPilot C++ course. Backtracking, which means choose, explore, undo, on three of the most asked interview questions: generating balanced parentheses (why a close bracket must never come before an open one), combination sum (why the same coins get counted again in a different order, and the start index that fixes it), and N-Queens (why checking the board only at the end runs out of time, and the column and diagonal arrays that check a square in one step).
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. The compiler stops a program that runs too long (Time Limit Exceeded, TLE), like an online judge.
Real-life pictures
| In real life | In C++ |
|---|---|
| A maze: at a dead end you walk back to the last fork and try the next way | backtracking: undo the last choice, try the next one |
A lift: ( = someone gets in, ) = someone gets out |
building a string of brackets |
| Nobody can get out of an empty lift | add ) only while close < open |
| Stop writing a sequence the moment it is impossible | pruning: cut a branch early |
| Paying exactly ₹8 with ₹2, ₹3 and ₹5 coins | combination sum |
| 2 + 3 + 3 and 3 + 2 + 3 are the same handful of coins | a multiset: order does not matter |
| Pick coins smallest first, never go back to a smaller coin | a start index i |
| ₹5 left and the next coin is ₹6? Every later coin is bigger too | sorted coins, break |
| An exam hall: no two students in the same row, column or diagonal | N-Queens |
| Tear up a seating plan the moment two students can see each other's papers | check a square before placing |
Backtracking in one minute: choose, explore, undo
You walk through a maze. At every fork you pick a way. At a dead end, you walk back to the last fork and try the next way. That walk back is backtracking. In code it is a recursive function, and it always has the same shape:
solve(state):
if the answer is complete: record it, return
for each choice:
if it can't work: skip it // PRUNING
make the choice // choose
solve(next state) // explore
undo the choice // undo
- Choose: change the shared state (push a bracket, push a coin, place a queen, mark a cell).
- Explore: recurse to fill in the rest.
- Undo: put the state back exactly as it was, so the next choice starts clean. Forgetting this is the most common bug (see the mistakes table).
- Pruning: before you make a choice, if it clearly cannot lead to an answer, skip it. A pruned branch is never built, and neither is anything below it.
All the calls together form a recursion tree: the root is the empty start, every branch is one choice, and every leaf is a place where the recursion stops (a full answer, or a dead end). Pruning does not change the shape of the code; it only changes where you check. Check early, and whole subtrees disappear.
Q1: Generate every balanced string of n pairs
Problem. Given n, print every string of n ( and n ) that is balanced, then how many there are. Balanced means: reading left to right, the number of ) never passes the number of ( (the lift is never emptier than empty). For big n, print only the count.
| Input | Output |
|---|---|
1 |
(), 1 string |
2 |
(()) ()(), 2 strings |
3 |
((())) (()()) (())() ()(()) ()()(), 5 strings |
14 |
count only: 2674440 strings |
Think out loud. Input: one number n. Output: the strings, then the count. Every answer has length 2n. We build it one bracket at a time and keep two counters, open and close. Edge cases: n = 1; big n (14), where printing would flood the screen, so the program prints strings only when n ≤ 4.
The obvious attempt: add ( while open < n and ) while close < n
#include <iostream>
#include <string>
using namespace std;
int n, cnt = 0;
void gen(string& cur, int open, int close) {
if ((int)cur.size() == 2 * n) { // base case: full length
if (n <= 4) cout << cur << " ";
cnt++;
return;
}
if (open < n) { // room for another (
cur.push_back('(');
gen(cur, open + 1, close);
cur.pop_back(); // undo
}
if (close < n) { // room for another )
cur.push_back(')');
gen(cur, open, close + 1);
cur.pop_back(); // undo
}
}
int main() {
cin >> n;
string cur;
gen(cur, 0, 0);
cout << "\n" << cnt << " strings\n";
return 0;
}
Input 2:
(()) ()() ())( )(() )()( ))((
6 strings
Six strings, and only two are balanced. ())( closes on step 3 with nobody inside. )(() and )()( and ))(( start with a close: the lift goes negative on the very first step. Four of the six are impossible.
Why it fails
close < n only stops us at n closes. It happily lets a ) come first, with nobody inside: ) → )( → )(( ... So the program built every mix of n opens and n closes. There are C(2n, n) of them ("2n choose n": pick which n of the 2n places hold a (): 6 for n = 2, 20 for n = 3, 70 for n = 4, and 40,116,600 for n = 14. It printed all of them, balanced or not.
Fix: add ) only while close < open
One condition changes. Someone can get out only if someone is inside: add a ) only while close < open. A broken string is never even started, so every string the recursion finishes is an answer. Nothing is wasted.
#include <iostream>
#include <string>
using namespace std;
int n, cnt = 0;
void gen(string& cur, int open, int close) {
if ((int)cur.size() == 2 * n) { // base case: full length
if (n <= 4) cout << cur << " ";
cnt++;
return;
}
if (open < n) { // room for another (
cur.push_back('(');
gen(cur, open + 1, close);
cur.pop_back(); // undo
}
if (close < open) { // only close what is open
cur.push_back(')');
gen(cur, open, close + 1);
cur.pop_back(); // undo
}
}
int main() {
cin >> n;
string cur;
gen(cur, 0, 0);
cout << "\n" << cnt << " strings\n";
return 0;
}
Input 2:
(()) ()()
2 strings
Input 3:
((())) (()()) (())() ()(()) ()()()
5 strings
Input 1:
()
1 strings
Input 14 (count only, so the first line is empty), in a blink:
2674440 strings
(int)cur.size() == 2 * n is the base case. We do not need to check open == n there: close < open ≤ n and the length is 2n, so open and close are both n. The program also passes cur by reference and undoes each push_back with pop_back, so there is only one string in memory the whole time.
Complexity. The number of answers is the Catalan number C(2n, n) / (n + 1): 1, 2, 5, 14, 42, ... (2,674,440 for n = 14). The pruned tree builds only those, each of length 2n, so the time is about O(Catalan(n) · n), roughly 4ⁿ / √n strings, against C(2n, n) for the obvious attempt. Space: O(n), the string and the recursion stack are at most 2n deep.
Q2: Combination sum
Problem. Given n different coins and a target, print every combination of coins that adds up to the target, each combination once. A coin can be used as many times as you like. Each answer is a multiset: like a set, but an item can repeat, and the order inside does not matter, so [2 3 3] and [3 2 3] are the same answer.
| Input (n target / coins) | Output |
|---|---|
3 8 / 2 3 5 |
[2 2 2 2] [2 3 3] [3 5] |
4 10 / 2 3 5 6 |
[2 2 2 2 2] [2 2 3 3] [2 2 6] [2 3 5] [5 5] |
2 1 / 2 3 |
no way |
Think out loud. Input: n and the target, then n coins. Output: every combination in brackets, or no way. We keep rem, the amount still to pay, and a vector cur of the coins in our hand. rem == 0 means we paid exactly. Edge cases: no way at all (target 1), a coin bigger than the target.
The obvious attempt: try every coin at every step
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cnt = 0;
void comb(const vector<int>& c, int start, int rem, vector<int>& cur) {
if (rem == 0) { // paid exactly
cout << "[";
for (int k = 0; k < (int)cur.size(); k++)
cout << (k ? " " : "") << cur[k];
cout << "] ";
cnt++;
return;
}
for (int i = 0; i < (int)c.size(); i++) {
if (c[i] > rem) continue; // too big: skip it
cur.push_back(c[i]);
comb(c, i, rem - c[i], cur); // the same coin may repeat
cur.pop_back(); // undo
}
}
int main() {
int n, target;
cin >> n >> target;
vector<int> c(n);
for (int& x : c) cin >> x;
sort(c.begin(), c.end());
vector<int> cur;
comb(c, 0, target, cur);
if (cnt == 0) cout << "no way";
cout << "\n";
return 0;
}
Input 3 8 / 2 3 5:
[2 2 2 2] [2 3 3] [3 2 3] [3 3 2] [3 5] [5 3]
Six answers for three real ones. [2 3 3], [3 2 3] and [3 3 2] are the same handful of coins counted in three orders, and so are [3 5] and [5 3]. (The start parameter is passed, but the loop ignores it.)
Why it fails
After picking a 3, the next step can still pick a 2: [3 2 3]. But [2 3 3] was already found. The loop starts at 0 every time, so smaller coins come back after bigger ones, and every order of the same coins becomes a new answer. With bigger targets this is not just wrong, it also does far more work, because every order is explored.
Fix: a start index, and break when a coin is too big
Each call only tries coins from position start onward, and passes its own i down. The same coin may repeat (we pass i, not i + 1), but a smaller coin never comes back. Every answer comes out in one order: smallest first. And since the coins are sorted, when c[i] > rem, every coin after it is bigger too, so break instead of continue. That is pruning again.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cnt = 0;
void comb(const vector<int>& c, int start, int rem, vector<int>& cur) {
if (rem == 0) { // paid exactly
cout << "[";
for (int k = 0; k < (int)cur.size(); k++)
cout << (k ? " " : "") << cur[k];
cout << "] ";
cnt++;
return;
}
for (int i = start; i < (int)c.size(); i++) {
if (c[i] > rem) break; // sorted: the rest are bigger
cur.push_back(c[i]);
comb(c, i, rem - c[i], cur); // the same coin may repeat
cur.pop_back(); // undo
}
}
int main() {
int n, target;
cin >> n >> target;
vector<int> c(n);
for (int& x : c) cin >> x;
sort(c.begin(), c.end());
vector<int> cur;
comb(c, 0, target, cur);
if (cnt == 0) cout << "no way";
cout << "\n";
return 0;
}
Input 3 8 / 2 3 5:
[2 2 2 2] [2 3 3] [3 5]
Input 4 10 / 2 3 5 6:
[2 2 2 2 2] [2 2 3 3] [2 2 6] [2 3 5] [5 5]
Input 2 1 / 2 3:
no way
break is only correct because main sorts the coins first. On unsorted coins, a big coin early in the list would stop the loop before a smaller coin later on.
Complexity. The time depends on how many answers and dead ends there are: roughly exponential in target / smallest coin (each level of the tree tries up to n coins, and the tree is at most target / smallest deep), but the start index removes every repeated order and break cuts the branches that are too big. Space: O(target / smallest coin), the deepest the stack and cur can go (four 2s for ₹8).
Q3: N-Queens: in how many ways?
Problem. Given n, count the ways to place n queens on an n × n chessboard so that no two attack each other. A queen attacks along its row, its column and both diagonals: exactly the exam-hall rule, no two students in the same row, column or diagonal.
| Input | Output |
|---|---|
1 |
1 ways |
2 |
0 ways |
3 |
0 ways |
4 |
2 ways |
8 |
92 ways |
12 |
14200 ways |
The two boards for n = 4 (Q is a queen; they are printed by practice question 2):
.Q.. ..Q.
...Q Q...
Q... ...Q
..Q. .Q..
Think out loud. Two queens in the same row would attack, so there is exactly one queen per row. That means we only choose a column for each row: col[r]. Two queens in rows r1 and r2 attack if they share a column (col[r1] == col[r2]) or a diagonal: on a diagonal, the column gap equals the row gap (|col[r1] - col[r2]| == r2 - r1). Edge cases: n = 1 (one way), n = 2 and 3 (no way at all), and n = 12.
The obvious attempt: fill every row, check the whole board at the end
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int n, cnt = 0;
vector<int> col; // col[r] = column of row r's queen
bool ok() { // check the WHOLE board
for (int r1 = 0; r1 < n; r1++)
for (int r2 = r1 + 1; r2 < n; r2++)
if (col[r1] == col[r2] ||
abs(col[r1] - col[r2]) == r2 - r1) return false;
return true;
}
void place(int r) {
if (r == n) { if (ok()) cnt++; return; }
for (int c = 0; c < n; c++) {
col[r] = c; // try every column
place(r + 1);
}
}
int main() {
cin >> n;
col.assign(n, 0);
place(0);
cout << cnt << " ways\n";
return 0;
}
Input 4:
2 ways
Input 8:
92 ways
Both correct. Input 12: the compiler stops it.
Time Limit Exceeded
Why it fails
The program fills every row with every column before it checks anything: n choices per row, n rows, so nⁿ boards, and each check costs O(n²). For n = 12 that is 12¹² = 8,916,100,448,256 boards, almost nine trillion. Most of them were dead much earlier: if rows 0 and 1 both use column 0, the board is already wrong, but the program still fills rows 2 to 11 in every possible way (12¹⁰ boards) and only then notices.
Fix: backtracking, check a square before placing
Check a square before placing a queen there. A dead board is never continued. To make the check one step, keep three arrays of bool:
same column: usedCol[c]
same / diagonal: r + c is the same → usedD1[r + c] (0 .. 2n-2)
same \ diagonal: r - c is the same → usedD2[r - c + n - 1] (0 .. 2n-2)
- On a
/diagonal (going down to the left), each step down adds 1 to r and takes 1 from c, so r + c stays the same. It goes from 0 (top-left) to 2n − 2 (bottom-right). - On a
\diagonal (going down to the right), r and c both grow by 1, so r − c stays the same. But r − c goes from −(n − 1) (top-right, r = 0, c = n − 1) to n − 1. It can be negative, and a negative index into a vector reads memory outside it: that is undefined behaviour (the program may crash, give a wrong answer, or seem to work). Adding n − 1 shifts the range to 0 .. 2n − 2, which is exactly the size of the array, sor - c + n - 1is never negative and never too big.
Both diagonal arrays have 2n − 1 entries. Mark all three when you place a queen, and unmark all three after the call. Choose, explore, undo.
#include <iostream>
#include <vector>
using namespace std;
int n, cnt = 0;
vector<bool> usedCol, usedD1, usedD2;
void place(int r) {
if (r == n) { cnt++; return; } // every row has a queen
for (int c = 0; c < n; c++) {
if (usedCol[c] || usedD1[r + c] || usedD2[r - c + n - 1])
continue; // attacked: prune
usedCol[c] = usedD1[r + c] = usedD2[r - c + n - 1] = true;
place(r + 1);
usedCol[c] = usedD1[r + c] = usedD2[r - c + n - 1] = false;
}
}
int main() {
cin >> n;
usedCol.assign(n, false);
usedD1.assign(2 * n - 1, false); // r + c: 0 .. 2n-2
usedD2.assign(2 * n - 1, false); // r - c + n - 1: 0 .. 2n-2
place(0);
cout << cnt << " ways\n";
return 0;
}
Input 12, in a blink:
14200 ways
Input 4:
2 ways
Input 3:
0 ways
Input 8:
92 ways
Input 2:
0 ways
Input 1:
1 ways
Complexity. The worst case is still about O(n!): row 0 has n columns, row 1 at most n − 1 free columns, and so on. But the diagonal checks cut far more, and in practice the tree is a tiny fraction of n! and nothing like nⁿ. Each check is O(1) thanks to the three arrays. Space: O(n), three arrays of about 2n and a recursion stack n deep.
Complexity summary
| Program | Time | Extra space |
|---|---|---|
parentheses, ) while close < n |
builds every mix: C(2n, n), n = 14: 40,116,600, wrong | O(n) |
parentheses, ) while close < open |
only the answers: Catalan(n), n = 14: 2,674,440 | O(n) |
| combination sum, loop from 0 | every order of every handful, wrong | O(target / smallest) |
combination sum, start index + break |
each multiset once, dead branches cut | O(target / smallest) |
| N-Queens, check at the end | O(nⁿ · n²), n = 12: 8.9 trillion boards: TLE | O(n) |
| N-Queens, column + diagonal arrays | at most O(n!), far less in practice: n = 12 in a blink | O(n) |
| n | C(2n, n): every mix | Catalan(n): balanced |
|---|---|---|
| 2 | 6 | 2 |
| 3 | 20 | 5 |
| 4 | 70 | 14 |
| 14 | 40,116,600 | 2,674,440 |
| n | nⁿ boards (check at the end) | answers |
|---|---|---|
| 4 | 256 | 2 |
| 8 | 16,777,216 | 92 |
| 12 | 8,916,100,448,256 | 14,200 |
Rule of thumb: prune, then recurse. The earlier the check, the more of the tree never gets built.
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
if (close < n) add ) |
no error: (()) ()() ())( )(() )()( ))((, 6 strings |
closes before opening | if (close < open) |
| loop from 0 in combination sum | no error: [2 3 3] [3 2 3] [3 3 2] ... |
every order counted | start index: for (int i = start; ...) |
| check the board at the end | Time Limit Exceeded for n = 12 |
nⁿ boards | check before placing |
usedD2[r - c] |
undefined behaviour (here it even printed 2 ways, 92 ways, by luck) |
r − c can be negative | usedD2[r - c + n - 1] |
forgetting cur.pop_back() (no undo) |
(()), then 1 strings for n = 2 |
the string keeps old brackets | undo every choice |
break on unsorted coins |
answers go missing | a smaller coin may come later | sort first, or continue |
comb(c, i + 1, ...) when a coin may repeat |
[3 5] only, for ₹8 with 2 3 5 |
each coin used at most once | pass i to allow repeats |
forgetting to unmark visited in the maze |
only DDRDRR, one path is lost |
a cell stays blocked for later paths | visited[nr][nc] = false; after the call |
The r - c bug is the dangerous one, because it may look fine. With usedD2[r - c] (array size 2n − 1) the program printed the right counts here for 4, 8 and 12, purely by luck of what sat in memory next to the vector. With usedD2.at(r - c), which checks the index, the truth shows up at once for n = 4:
terminate called after throwing an instance of 'std::out_of_range'
what(): vector<bool>::_M_range_check: __n (which is 18446744073709551615) >= this->size() (which is 7)
r − c = −1 became 18446744073709551615 because at() takes an unsigned size_t, and −1 wraps around to the biggest value. The program aborted (exit code 134, SIGABRT), and the compiler shows it as a runtime error.
The missing undo, G without the cur.pop_back(); lines, input 2:
(())
1 strings
After the first answer (()) was printed, its brackets stayed in cur, so cur.size() was already past 2n and never equal to it again: every later string was lost.
Mini project: a Sudoku solver
Fill a 9 × 9 grid so every row, every column and every 3 × 3 box holds 1 to 9 once. It is the exam hall again with three rules instead of two: keep rowUsed, colUsed and boxUsed arrays (box number (r / 3) * 3 + c / 3), go cell by cell, skip any digit that is already used (prune), place it, recurse, and undo when the rest fails. Here we stop at the first full grid: solve returns true all the way up, so nothing is undone after success.
#include <iostream>
#include <string>
using namespace std;
int g[9][9];
bool rowUsed[9][10], colUsed[9][10], boxUsed[9][10];
long long tries = 0;
int box(int r, int c) { return (r / 3) * 3 + c / 3; }
void setCell(int r, int c, int d, bool on) {
rowUsed[r][d] = colUsed[c][d] = boxUsed[box(r, c)][d] = on;
g[r][c] = on ? d : 0;
}
bool solve(int pos) {
if (pos == 81) return true; // every cell filled
int r = pos / 9, c = pos % 9;
if (g[r][c] != 0) return solve(pos + 1); // given digit: move on
for (int d = 1; d <= 9; d++) {
if (rowUsed[r][d] || colUsed[c][d] || boxUsed[box(r, c)][d]) continue; // prune
tries++;
setCell(r, c, d, true); // choose
if (solve(pos + 1)) return true; // explore
setCell(r, c, d, false); // undo
}
return false; // dead end: go back
}
int main() {
for (int r = 0; r < 9; r++) {
string line;
cin >> line;
for (int c = 0; c < 9; c++) {
int d = line[c] == '.' ? 0 : line[c] - '0';
if (d) setCell(r, c, d, true);
}
}
if (!solve(0)) { cout << "no solution\n"; return 0; }
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) cout << g[r][c] << (c % 3 == 2 && c < 8 ? " | " : c < 8 ? " " : "");
cout << "\n";
if (r % 3 == 2 && r < 8) cout << "------+-------+------\n";
}
cout << tries << " digits tried\n";
return 0;
}
Input (. is an empty cell):
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
Output:
5 3 4 | 6 7 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | 7 6 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9
4208 digits tried
Only 4,208 digits were placed for 51 empty cells: the three checks cut almost every branch before it was built.
Practice questions (with solutions)
1. Your turn: every path through a maze. An n × n grid of 1 (open) and 0 (wall). Print every path from the top-left to the bottom-right, moving D (down), L (left), R (right) or U (up), never visiting a cell twice. Print the moves of each path in that order (D L R U), or no path.
1 0 0 0
1 1 0 1 → DDRDRR DRDDRR
1 1 0 0
0 1 1 1
Solution
Mark a cell visited, try the four moves, and unmark it on the way back. Choose, explore, undo. Trying the moves in the order D L R U prints the paths in alphabetical order.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int n, cnt = 0;
vector<vector<int>> g;
vector<vector<bool>> visited;
string path;
const int dr[4] = {1, 0, 0, -1}; // D L R U (alphabetical order)
const int dc[4] = {0, -1, 1, 0};
const char name[4] = {'D', 'L', 'R', 'U'};
void walk(int r, int c) {
if (r == n - 1 && c == n - 1) { // reached the bottom-right
cout << path << " ";
cnt++;
return;
}
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue; // off the grid
if (g[nr][nc] == 0 || visited[nr][nc]) continue; // wall or used
visited[nr][nc] = true; // choose
path.push_back(name[k]);
walk(nr, nc); // explore
path.pop_back(); // undo
visited[nr][nc] = false;
}
}
int main() {
cin >> n;
g.assign(n, vector<int>(n));
for (auto& row : g)
for (int& x : row) cin >> x;
visited.assign(n, vector<bool>(n, false));
if (g[0][0] == 1) {
visited[0][0] = true;
walk(0, 0);
}
if (cnt == 0) cout << "no path";
cout << "\n";
return 0;
}
Input 4 / the grid above:
DDRDRR DRDDRR
Input 2 / 1 0 / 0 1 (the only way is diagonal, which is not a move):
no path
Time: at most 4 choices per step, about O(4^(n²)) in the worst case, far less with walls; space O(n²) for visited and the stack.
2. Print every N-Queens board for n = 4.
Solution
The Q3 program plus a board of strings: put 'Q' on choose, put '.' back on undo, and print the board at the base case.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int n, cnt = 0;
vector<bool> usedCol, usedD1, usedD2;
vector<string> board;
void place(int r) {
if (r == n) { // a full board: print it
cnt++;
cout << "Board " << cnt << ":\n";
for (const string& row : board) cout << row << "\n";
cout << "\n";
return;
}
for (int c = 0; c < n; c++) {
if (usedCol[c] || usedD1[r + c] || usedD2[r - c + n - 1]) continue;
usedCol[c] = usedD1[r + c] = usedD2[r - c + n - 1] = true;
board[r][c] = 'Q'; // choose
place(r + 1); // explore
board[r][c] = '.'; // undo
usedCol[c] = usedD1[r + c] = usedD2[r - c + n - 1] = false;
}
}
int main() {
cin >> n;
usedCol.assign(n, false);
usedD1.assign(2 * n - 1, false);
usedD2.assign(2 * n - 1, false);
board.assign(n, string(n, '.'));
place(0);
cout << cnt << " boards\n";
return 0;
}
Input 4:
Board 1:
.Q..
...Q
Q...
..Q.
Board 2:
..Q.
Q...
...Q
.Q..
2 boards
3. Combination sum where each coin is used at most once. The input may contain the same coin value more than once (two ₹1 coins are two coins), but each answer must be printed once.
Solution
Two changes to Q2. Pass i + 1, so a coin is never used twice. And after sorting, equal coins sit next to each other: at the same step (the same loop), skip a coin equal to the one just tried (i > start && c[i] == c[i - 1]), because it would build exactly the same answers again. It is still allowed one level deeper, so [1 1 6] is found.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cnt = 0;
void comb(const vector<int>& c, int start, int rem, vector<int>& cur) {
if (rem == 0) {
cout << "[";
for (int k = 0; k < (int)cur.size(); k++)
cout << (k ? " " : "") << cur[k];
cout << "] ";
cnt++;
return;
}
for (int i = start; i < (int)c.size(); i++) {
if (i > start && c[i] == c[i - 1]) continue; // same value at this step: skip
if (c[i] > rem) break; // sorted: the rest are bigger
cur.push_back(c[i]);
comb(c, i + 1, rem - c[i], cur); // i + 1: each coin once
cur.pop_back();
}
}
int main() {
int n, target;
cin >> n >> target;
vector<int> c(n);
for (int& x : c) cin >> x;
sort(c.begin(), c.end());
vector<int> cur;
comb(c, 0, target, cur);
if (cnt == 0) cout << "no way";
cout << "\n";
return 0;
}
Input 7 8 / 10 1 2 7 6 1 5:
[1 1 6] [1 2 5] [1 7] [2 6]
Input 5 5 / 2 5 2 1 2:
[1 2 2] [5]
Input 3 8 / 2 3 5 (each coin once now, so [2 2 2 2] and [2 3 3] are gone):
[3 5]
Without the skip line, the first test prints duplicates:
[1 1 6] [1 2 5] [1 7] [1 2 5] [1 7] [2 6]
4. Word search in a letter grid. Given a grid of letters and some words, say for each word whether it can be spelled by walking up, down, left or right, using each cell at most once.
Solution
Start from every cell. If the letter matches, mark the cell (replace it with #), try the four neighbours for the next letter, and put the letter back on the way out. A wrong letter, the edge of the grid or a used cell is a dead end: prune.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int R, C;
vector<string> g;
bool found(int r, int c, const string& w, int i) {
if (i == (int)w.size()) return true; // every letter matched
if (r < 0 || r >= R || c < 0 || c >= C) return false;
if (g[r][c] != w[i]) return false; // wrong letter (or '#': used)
char saved = g[r][c];
g[r][c] = '#'; // choose: mark as used
bool ok = found(r + 1, c, w, i + 1) || found(r - 1, c, w, i + 1) ||
found(r, c + 1, w, i + 1) || found(r, c - 1, w, i + 1);
g[r][c] = saved; // undo
return ok;
}
bool exists(const string& w) {
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
if (found(r, c, w, 0)) return true;
return false;
}
int main() {
cin >> R >> C;
g.resize(R);
for (string& row : g) cin >> row;
string w;
while (cin >> w) cout << w << ": " << (exists(w) ? "yes" : "no") << "\n";
return 0;
}
Input:
3 4
ABCE
SFCS
ADEE
ABCCED SEE ABCB
Output:
ABCCED: yes
SEE: yes
ABCB: no
ABCB fails because the only B is already used by the time we need the second one. Time: O(R · C · 4^L) for a word of length L; space O(L) for the stack.
Quick quiz
1. How many strings? (the episode quiz)
#include <iostream>
#include <string>
using namespace std;
int cnt = 0;
void gen(string s, int open, int close, int n) {
if ((int)s.size() == 2 * n) { cnt++; return; }
if (open < n) gen(s + '(', open + 1, close, n);
if (close < open) gen(s + ')', open, close + 1, n);
}
int main() {
gen("", 0, 0, 4);
cout << cnt << "\n";
return 0;
}
(A) 14 (B) 16 (C) 8 (D) 70
Answer
(A) 14. Only balanced strings are built: for n = 4 there are 14 (1, 2, 5, 14, 42, ...: the Catalan numbers). 70 would be every mix of four opens and four closes, balanced or not.
14
2. The obvious attempt from Q1 () while close < n) with input 3 prints how many strings?
(A) 5 (B) 6 (C) 20 (D) 14
Answer
(C) 20. Every mix of 3 opens and 3 closes: C(6, 3) = 20. Only 5 of them are balanced. The last line of the output:
20 strings
3. The fixed Q2 program with input 3 7 / 2 3 5 prints?
(A) [2 2 3] [2 5] (B) [2 2 3] [2 3 2] [3 2 2] [2 5] [5 2] (C) [2 5] (D) no way
Answer
(A). Smallest first, each handful once. (B) is what the loop from 0 would do; (C) is what i + 1 would do.
[2 2 3] [2 5]
4. The fixed Q3 program with input 6 prints?
(A) 0 ways (B) 4 ways (C) 10 ways (D) 6 ways
Answer
(B) 4 ways. The counts are not monotonic: n = 5 gives 10, but n = 6 only 4.
4 ways
5. For n = 8, what range does r - c + n - 1 cover, and how big must usedD2 be?
Answer
r − c goes from −7 (row 0, column 7) to 7 (row 7, column 0). Adding n − 1 = 7 gives 0 to 14, so usedD2 needs 15 entries, which is 2n − 1.
Interview questions
- What is backtracking? Building an answer one choice at a time, and undoing the last choice to try the next one when a path is finished or dead. Choose, explore, undo.
- What is pruning? Skipping a choice the moment it cannot lead to an answer, so the whole branch below it is never built.
- Backtracking vs plain recursion? Backtracking is recursion over choices with a shared state that is changed before the call and restored after it.
- How many balanced strings of n pairs are there? The n-th Catalan number, C(2n, n) / (n + 1): 1, 2, 5, 14, 42, ...
- What two conditions generate only balanced strings? Add
(whileopen < n; add)whileclose < open. - How do you avoid repeated orders in combination sum? Sort, and pass a start index: each call only tries coins from
ionward. - Combination sum: coin used many times vs once? Recurse with
ito allow repeats; withi + 1for at most once, and skip equal neighbours at the same level when the input has duplicates. - Why
breakand notcontinuewhen a coin is too big? The coins are sorted, so every later coin is bigger too. - How do you check N-Queens in O(1)? Three
boolarrays: columnc, diagonalr + c, anti-diagonalr - c + n - 1. - Why
+ n - 1? r − c ranges from −(n − 1) to n − 1; a negative index is undefined behaviour. The shift maps it to 0 .. 2n − 2. - Time of N-Queens? At most O(n!) with backtracking, against O(nⁿ) for "fill everything, check at the end"; space O(n).
- Why must you undo? The state is shared by every branch; if a choice is not undone, the next branch starts with stale data (the missing
pop_backprinted only 1 string). - All answers vs the first answer? For all answers, record and keep going; for the first (Sudoku), return
trueand stop at once.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Backtracking | Build an answer choice by choice; undo the last choice to try the next | choose, explore, undo |
| Choose / explore / undo | Change the state, recurse, put the state back | push_back, gen(...), pop_back |
| Pruning | Cut a branch the moment it cannot lead to an answer | if (close < open) |
| Recursion tree | All the calls of a recursive function drawn as a tree | root = empty string |
| Branch | One choice from a node of the tree, and everything below it | adding ( |
| Leaf | A call that does not recurse further: an answer or a dead end | (()) |
| Dead end | A state from which no answer can be reached | a ) with nobody inside |
| Base case | The condition that ends the recursion | cur.size() == 2 * n |
| Balanced parentheses | Brackets where ) never outnumbers ( from the left, and the counts end equal |
(()()) |
| C(2n, n) | "2n choose n": the number of ways to pick n places out of 2n | 6 for n = 2 |
| Catalan number | C(2n, n) / (n + 1): the number of balanced strings of n pairs | 1, 2, 5, 14, 42 |
| Combination sum | Every multiset of coins that adds up to a target | ₹8 = 2 + 3 + 3 |
| Multiset | Like a set, but items can repeat; order does not matter | [2 3 3] = [3 2 3] |
| Combination | A choice of items where order does not matter | [3 5] |
| Permutation | An ordering of items, where order matters | [3 5] ≠ [5 3] |
| Start index | The first position a call may choose from, so earlier items never come back | for (int i = start; ...) |
| Skip equal neighbours | After sorting, at one level, skip a value equal to the one just tried | i > start && c[i] == c[i - 1] |
| N-Queens | Place n queens on an n × n board so that none attacks another | n = 8: 92 ways |
Diagonal (/) |
Squares where r + c is the same | usedD1[r + c] |
Anti-diagonal (\) |
Squares where r − c is the same | usedD2[r - c + n - 1] |
| r + c and r − c | Diagonal numbers: r + c is 0 .. 2n − 2; r − c is −(n − 1) .. n − 1, shifted by n − 1 | n = 4: 7 diagonals each way |
| Undefined behaviour (UB) | Code the C++ standard gives no meaning to; anything can happen | usedD2[-1] |
| Out of range | An index outside a container's size | .at(-1) throws std::out_of_range |
| Visited array | Marks which cells the current path already uses | visited[r][c] = true |
| Exponential time | Time that multiplies with every extra step, like 2ⁿ or 4ⁿ | the recursion tree doubles each level |
| nⁿ | n multiplied by itself n times: n choices in each of n rows | 12¹² ≈ 8.9 trillion |
| n! | n factorial: n · (n − 1) · ... · 1 | 12! = 479,001,600 |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | N-Queens checked at the end, n = 12 |
Summary
- Backtracking = choose, explore, undo. Pruning = skip a choice the moment it cannot work, so its whole branch is never built.
- Balanced parentheses:
(whileopen < n,)whileclose < open. Only the Catalan(n) answers are built, not all C(2n, n) mixes. - Combination sum: sort, pass a start index (
ifor repeats,i + 1for each coin once), andbreakwhen a coin is bigger than what is left. - N-Queens: one queen per row; check
usedCol[c],usedD1[r + c]andusedD2[r - c + n - 1]before placing.+ n - 1keeps the index from going negative. n = 12: 14,200 ways in a blink instead of TLE.
Next episode: Linked list questions: build a list with a Node struct, insert at the head and the tail, delete by value, and free the memory.