SyntaxPilot
Courses/C++ Coding Questions/Lesson 21
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ Coding Questions · Lesson 21 of 30

Backtracking questions

generate balanced parenthesescombination sumN-Queens count; pruning and the recursion tree

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, so r - c + n - 1 is 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

  1. 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.
  2. What is pruning? Skipping a choice the moment it cannot lead to an answer, so the whole branch below it is never built.
  3. Backtracking vs plain recursion? Backtracking is recursion over choices with a shared state that is changed before the call and restored after it.
  4. How many balanced strings of n pairs are there? The n-th Catalan number, C(2n, n) / (n + 1): 1, 2, 5, 14, 42, ...
  5. What two conditions generate only balanced strings? Add ( while open < n; add ) while close < open.
  6. How do you avoid repeated orders in combination sum? Sort, and pass a start index: each call only tries coins from i onward.
  7. Combination sum: coin used many times vs once? Recurse with i to allow repeats; with i + 1 for at most once, and skip equal neighbours at the same level when the input has duplicates.
  8. Why break and not continue when a coin is too big? The coins are sorted, so every later coin is bigger too.
  9. How do you check N-Queens in O(1)? Three bool arrays: column c, diagonal r + c, anti-diagonal r - c + n - 1.
  10. 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.
  11. Time of N-Queens? At most O(n!) with backtracking, against O(nⁿ) for "fill everything, check at the end"; space O(n).
  12. 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_back printed only 1 string).
  13. All answers vs the first answer? For all answers, record and keep going; for the first (Sudoku), return true and 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: ( while open < n, ) while close < open. Only the Catalan(n) answers are built, not all C(2n, n) mixes.
  • Combination sum: sort, pass a start index (i for repeats, i + 1 for each coin once), and break when a coin is bigger than what is left.
  • N-Queens: one queen per row; check usedCol[c], usedD1[r + c] and usedD2[r - c + n - 1] before placing. + n - 1 keeps 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.