These are the notes for C++ Coding Questions, episode 20, placement practice for people who finished the SyntaxPilot C++ course. Recursion, a function that solves a problem by solving a smaller copy of the same problem, on three of the most asked interview questions: fast power a^b mod 1,000,000,007 (a loop that would take thirty years, and an int that quietly overflows), all subsets (why nested loops can't do it, and subsets that keep growing), and all permutations (the missing swap back, and why next_permutation needs a sort first).
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 dark cinema queue: "which number am I?" Ask the person in front and add 1; the first person just knows | recursion: a base case plus a smaller copy of the same question |
| The king's chessboard: 1 grain of rice on square 1, double on every next square | a^b, a huge number: keep only the remainder mod 1,000,000,007 |
| Square 32 holds 2^31 grains; square that number and you have square 63: 2^62 = 2^31 × 2^31 | fast power: a^b = a^(b/2) × a^(b/2), about 60 steps for b = 10^18 |
| A pizza shop: corn, paneer, olive, each topping out or in | subsets: 2 choices per item, 2^n subsets |
| Add onion: the menu doubles to 16 | one more item doubles the count |
| The cook puts a topping back on the shelf before the next pizza | backtracking: cur.pop_back() undoes the take |
| Asha, Ravi and Neha line up for a photo: who stands first, then who next | permutations: 3 × 2 × 1 = 6 orders, n! in general |
| After each photo, everyone goes back to their place | swap, recurse, swap back |
Recursion in one minute
#include <iostream>
using namespace std;
int place(int n) {
if (n == 1) return 1; // base case: the first person knows
return place(n - 1) + 1; // ask the person in front, add 1
}
int main() {
int n;
cin >> n;
cout << "You are number " << place(n) << "\n";
return 0;
}
Input 5:
You are number 5
- Base case: the smallest question, whose answer is known directly (
n == 1→ 1). Every recursion needs one. - Smaller copy: every other call asks the same question about a smaller input (
place(n - 1)), so it moves towards the base case. - Call stack: each call waits, with its own
n, until the smaller call returns.place(5)waits forplace(4), which waits forplace(3)... down toplace(1), which returns 1; then they finish in reverse order: 2, 3, 4, 5. - Depth: how many calls wait at the same time (5 here). The stack has a fixed size (often 8 MB on Linux), so a very deep recursion runs out of it.
- Stack overflow: no base case, or a problem that never gets smaller, means the calls never stop. The stack fills up and the program crashes.
Here is place with the base case removed. -Wall warns about it:
#include <iostream>
using namespace std;
int place(int n) {
return place(n - 1) + 1; // no base case: never stops
}
int main() {
int n;
cin >> n;
cout << "You are number " << place(n) << "\n";
return 0;
}
main.cpp: In function ‘int place(int)’:
main.cpp:4:5: warning: infinite recursion detected [-Winfinite-recursion]
4 | int place(int n) {
| ^~~~~
main.cpp:5:17: note: recursive call
5 | return place(n - 1) + 1; // no base case: never stops
| ~~~~~^~~~~~~
With -O2, g++ turned this endless recursion into an endless loop, so on input 5 it never prints anything and is stopped with Time Limit Exceeded. Without optimisation (-O0), the same program crashes with a segmentation fault: the stack overflowed. Either way it is broken; read the warning.
A real stack overflow, with a correct base case but a depth of 100,000,000:
#include <iostream>
using namespace std;
long long sumTo(int n) {
if (n == 0) return 0; // base case
long long rest = sumTo(n - 1); // the call waits here
cout << ""; // some work after the call
return rest + n;
}
int main() {
int n;
cin >> n;
cout << sumTo(n) << "\n";
return 0;
}
Input 1000:
500500
Input 100000000:
Runtime Error (SIGSEGV)
A hundred million calls waiting at once need far more than the 8 MB stack, so the program is killed with a segmentation fault (signal 11) and prints nothing. Recursion is fine when the depth is small (log n, or n up to around 10^5); the three questions below have depth 60, n and n.
The modulo rule
Answers like 2^(10^18) have about 300,000,000,000,000,000 digits, so the question asks for the remainder after dividing by 1,000,000,007 (10^9 + 7, a prime that fits in an int, the standard choice in contests). One rule makes this possible:
(x · y) % m = ((x % m) · (y % m)) % m
So you take % MOD after every multiplication, and the numbers never grow past MOD − 1 = 1,000,000,006. But the product of two such numbers is about 10^18: it fits in a long long (up to about 9.2 · 10^18), not in an int (up to 2,147,483,647).
Q1: Fast power, a^b mod 1,000,000,007
Problem. Given a and b, print a^b % 1,000,000,007.
| Input | Output |
|---|---|
2 10 |
1024 |
3 13 |
1594323 |
2 1000000000000000000 |
719476260 |
Think out loud. Input: two numbers, b up to 10^18. Output: one number, the remainder. Edge cases: b = 0 (the answer is 1), b = 10^18 (no loop can do 10^18 steps), and overflow when two big remainders are multiplied.
The obvious attempt: multiply b times
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
long long power(long long a, long long b) {
long long ans = 1;
for (long long i = 0; i < b; i++)
ans = ans * a % MOD; // one multiply per step
return ans;
}
int main() {
long long a, b;
cin >> a >> b;
cout << power(a, b) << "\n";
return 0;
}
Input 2 10:
1024
Input 3 13:
1594323
Input 2 1000000000000000000:
Time Limit Exceeded
Why it fails
One multiplication per step is O(b). For b = 10^18 that is a billion billion multiplications; even at a billion a second, about thirty years.
The idea: halve the power (divide and conquer)
This is the king's rice trick. If you know a^(b/2), one multiplication gives a^b:
b even: a^b = a^(b/2) · a^(b/2) 2^10 = 2^5 · 2^5
b odd: a^b = a^(b/2) · a^(b/2) · a 2^5 = 2^2 · 2^2 · 2
In C++, b / 2 rounds down, so 5 / 2 is 2. The base case is b = 0 → 1. Every call halves b, so there are only about log₂ b calls: 10^18 reaches 0 after 60 halvings. Splitting a problem into a smaller one and building the answer from it is called divide and conquer; this algorithm is called fast power, binary exponentiation or modular exponentiation.
Trap 1: calling power twice
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
long long calls = 0;
long long power(long long a, long long b) {
calls++;
if (b == 0) return 1;
long long ans = power(a, b / 2) * power(a, b / 2) % MOD; // called TWICE
if (b % 2 == 1) ans = ans * a % MOD;
return ans;
}
int main() {
long long a, b;
cin >> a >> b;
cout << power(a, b) << "\n";
cout << calls << " calls\n";
return 0;
}
Input 2 10:
1024
31 calls
Input 3 13:
1594323
31 calls
Input 2 1000000000000000000:
Time Limit Exceeded
The answers are right, but power(a, b / 2) * power(a, b / 2) calls itself twice at every level: 1 + 2 + 4 + 8 + 16 = 31 calls for b = 10. The number of calls doubles at each of the ~log b levels, which is about 2b calls: back to O(b), and TLE again.
The same program with the call made once and kept in half:
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
long long calls = 0;
long long power(long long a, long long b) {
calls++;
if (b == 0) return 1;
long long half = power(a, b / 2); // called ONCE
long long ans = half * half % MOD;
if (b % 2 == 1) ans = ans * a % MOD;
return ans;
}
int main() {
long long a, b;
cin >> a >> b;
cout << power(a, b) << "\n";
cout << calls << " calls\n";
return 0;
}
Input 2 10:
1024
5 calls
Input 2 1000000000000000000:
719476260
61 calls
5 calls instead of 31, and only 61 calls for b = 10^18 (60 halvings, plus the base case).
Trap 2: fast power written with int
The episode's version: call once, but half, ans, a and MOD are int.
#include <iostream>
using namespace std;
const int MOD = 1000000007;
int power(int a, long long b) {
if (b == 0) return 1; // base case: a^0 = 1
int half = power(a, b / 2); // a^(b/2), computed ONCE
int ans = half * half % MOD;
if (b % 2 == 1) ans = ans * a % MOD; // odd b: one more a
return ans;
}
int main() {
long long a, b;
cin >> a >> b;
cout << power(a, b) << "\n";
return 0;
}
Input 2 10:
1024
Input 3 13:
1594323
Input 2 1000000000000000000:
0
Instant, but 0. 2 to any power can never leave a remainder of 0 when divided by an odd prime; the right answer is 719476260.
Why: half * half doesn't fit in an int
After % MOD, half can be as big as 1,000,000,006, so half * half can be about 10^18. An int holds at most 2,147,483,647 (about 2 · 10^9). Multiplying two ints is done in int, so the product overflows before % MOD ever runs.
Signed integer overflow is undefined behaviour in C++: the standard does not say what happens, and the compiler may assume it never happens. Here it gave a wrong answer, with no warning and no crash; another compiler, or another -O level, might give a different wrong answer. Never rely on what overflow "does".
The small tests passed because small numbers never overflow. Always test the biggest input too.
The fix: everything long long
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
long long power(long long a, long long b) {
if (b == 0) return 1; // base case: a^0 = 1
long long half = power(a, b / 2); // a^(b/2), computed ONCE
long long ans = half * half % MOD;
if (b % 2 == 1) ans = ans * a % MOD; // odd b: one more a
return ans;
}
int main() {
long long a, b;
cin >> a >> b;
cout << power(a, b) << "\n";
return 0;
}
Input 2 10:
1024
Input 3 13:
1594323
Input 2 1000000000000000000:
719476260
Correct and instant. (a must stay below MOD for ans * a to be safe; with big inputs, add a %= MOD; first.)
Complexity. Time O(log b) (about 60 calls for 10^18). Space O(log b), for the calls waiting on the stack. The loop version in practice question 4 needs only O(1) space.
Q2: Print every subset
Problem. Given n items, print every subset (in any order), then how many there are.
| Input | Output |
|---|---|
3 / corn paneer olive |
{} {olive} {paneer} {paneer olive} {corn} {corn olive} {corn paneer} {corn paneer olive}, 8 subsets |
4 / corn paneer olive onion |
16 subsets |
0 |
{}, 1 subset |
Think out loud. A subset is some of the items: maybe none, maybe all. Each item is out or in, 2 choices, so n items give 2 × 2 × ... = 2^n subsets. The set of all subsets is called the power set. Edge cases: n = 0 (only the empty set), n = 4 (16), and it must work for any n.
The obvious attempt: one loop per topping
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
vector<string> t(n);
for (auto& s : t) cin >> s;
int cnt = 0;
for (int a = 0; a < 2; a++) // topping 0: out / in
for (int b = 0; b < 2; b++) // topping 1: out / in
for (int c = 0; c < 2; c++) { // topping 2
vector<string> cur;
if (a) cur.push_back(t[0]);
if (b) cur.push_back(t[1]);
if (c) cur.push_back(t[2]);
cout << "{";
for (int k = 0; k < (int)cur.size(); k++)
cout << (k ? " " : "") << cur[k];
cout << "} ";
cnt++;
}
cout << "\n" << cnt << " subsets\n";
return 0;
}
Input 3 / corn paneer olive:
{} {olive} {paneer} {paneer olive} {corn} {corn olive} {corn paneer} {corn paneer olive}
8 subsets
Input 4 / corn paneer olive onion:
{} {olive} {paneer} {paneer olive} {corn} {corn olive} {corn paneer} {corn paneer olive}
8 subsets
Still 8, and onion is never in any of them.
Why it fails
Three loops make exactly three decisions. Four items need four nested loops, and n items need n, but the number of loops is fixed when you write the code. (And with n < 3, t[2] reads past the end of the vector.)
Recursion: one level per item
subsets(i): decide item i
if i == n: print cur // base case: all decided
skip t[i] → subsets(i + 1)
take t[i] → subsets(i + 1)
Each level of recursion acts like one more loop, as deep as n needs.
Attempt: skip and take, without undoing
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int cnt = 0;
void subsets(const vector<string>& t, int i, vector<string>& cur) {
if (i == (int)t.size()) { // base case: all decided
cout << "{";
for (int k = 0; k < (int)cur.size(); k++)
cout << (k ? " " : "") << cur[k];
cout << "} ";
cnt++;
return;
}
subsets(t, i + 1, cur); // skip t[i]
cur.push_back(t[i]); // take t[i]
subsets(t, i + 1, cur);
}
int main() {
int n;
cin >> n;
vector<string> t(n);
for (auto& s : t) cin >> s;
vector<string> cur;
subsets(t, 0, cur);
cout << "\n" << cnt << " subsets\n";
return 0;
}
Input 3 / corn paneer olive:
{} {olive} {olive paneer} {olive paneer olive} {olive paneer olive corn} {olive paneer olive corn olive} {olive paneer olive corn olive paneer} {olive paneer olive corn olive paneer olive}
8 subsets
Input 4 / corn paneer olive onion:
{} {onion} {onion olive} {onion olive onion} {onion olive onion paneer} {onion olive onion paneer onion} {onion olive onion paneer onion olive} {onion olive onion paneer onion olive onion} {onion olive onion paneer onion olive onion corn} {onion olive onion paneer onion olive onion corn onion} {onion olive onion paneer onion olive onion corn onion olive} {onion olive onion paneer onion olive onion corn onion olive onion} {onion olive onion paneer onion olive onion corn onion olive onion paneer} {onion olive onion paneer onion olive onion corn onion olive onion paneer onion} {onion olive onion paneer onion olive onion corn onion olive onion paneer onion olive} {onion olive onion paneer onion olive onion corn onion olive onion paneer onion olive onion}
16 subsets
The count is right (8, then 16), but the subsets keep growing, and olive appears again and again.
Why: the take was never undone
take olive → print {olive} → return ... cur is STILL {olive}
next branch takes paneer → {olive paneer} (olive should be gone)
There is only one cur, passed by reference and shared by every call. A change made in one branch leaks into the next one.
Fix: backtracking, undo before you return
The cook's rule: put the topping back on the shelf. Trying a choice, then undoing it to try the next one, is called backtracking.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int cnt = 0;
void subsets(const vector<string>& t, int i, vector<string>& cur) {
if (i == (int)t.size()) { // base case: all decided
cout << "{";
for (int k = 0; k < (int)cur.size(); k++)
cout << (k ? " " : "") << cur[k];
cout << "} ";
cnt++;
return;
}
subsets(t, i + 1, cur); // skip t[i]
cur.push_back(t[i]); // take t[i]
subsets(t, i + 1, cur);
cur.pop_back(); // undo the take
}
int main() {
int n;
cin >> n;
vector<string> t(n);
for (auto& s : t) cin >> s;
vector<string> cur;
subsets(t, 0, cur);
cout << "\n" << cnt << " subsets\n";
return 0;
}
Input 3 / corn paneer olive:
{} {olive} {paneer} {paneer olive} {corn} {corn olive} {corn paneer} {corn paneer olive}
8 subsets
Input 4 / corn paneer olive onion:
{} {onion} {olive} {olive onion} {paneer} {paneer onion} {paneer olive} {paneer olive onion} {corn} {corn onion} {corn olive} {corn olive onion} {corn paneer} {corn paneer onion} {corn paneer olive} {corn paneer olive onion}
16 subsets
Input 0:
{}
1 subsets
Eight, each one right; sixteen with onion; and for n = 0, just the empty set.
Complexity. 2^n subsets, each up to n items to print: time O(2^n · n). Space O(n): the recursion depth is n, and cur holds at most n items. For n = 20 that is already 1,048,576 subsets.
Q3: Print every permutation of a string
Problem. Given a string, print every permutation: the same letters in every different order.
| Input | Output |
|---|---|
abc |
abc acb bac bca cba cab (6 = 3 × 2 × 1) |
a |
a |
aab |
aab aba baa (each order once) |
Think out loud. n letters have n! (n factorial: n × (n − 1) × ... × 1) orders. Like the photo: choose who stands at place 0 (n choices), then place 1 (n − 1 left), and so on. Edge cases: one letter, and repeated letters.
The plan. perms(s, i) fills place i. For every j from i onward, swap s[j] into place i, and fill the rest with perms(s, i + 1). Base case: i == n, every place is filled, print s.
The obvious attempt: swap and recurse
#include <iostream>
#include <string>
using namespace std;
void perms(string& s, int i) {
if (i == (int)s.size()) { // base case: all placed
cout << s << " ";
return;
}
for (int j = i; j < (int)s.size(); j++) {
swap(s[i], s[j]); // s[j] stands at place i
perms(s, i + 1); // arrange the rest
}
}
int main() {
string s;
cin >> s;
perms(s, 0);
cout << "\n";
return 0;
}
Input abc:
abc acb cab cba abc acb
Six words, but abc and acb appear twice, and bac and bca never appear.
Why: the line was never put back
i = 0: j = 0 → abc ... the deeper calls leave s as acb
j = 1 swaps s[0], s[1] of acb → cab (we wanted b first: bac)
The loop assumes s is still abc, but the calls below it changed the string. Same bug as Q2: a change leaks into the next branch.
Fix: swap back after the call
#include <iostream>
#include <string>
using namespace std;
void perms(string& s, int i) {
if (i == (int)s.size()) { // base case: all placed
cout << s << " ";
return;
}
for (int j = i; j < (int)s.size(); j++) {
swap(s[i], s[j]); // s[j] stands at place i
perms(s, i + 1); // arrange the rest
swap(s[i], s[j]); // undo: back in place
}
}
int main() {
string s;
cin >> s;
perms(s, 0);
cout << "\n";
return 0;
}
Input abc:
abc acb bac bca cba cab
Input a:
a
Input aab:
aab aba aab aba baa baa
All six for abc, each once. For aab the swap method still prints six, with repeats: it treats the two as as different letters. Practice question 2 prints each order once.
Complexity. n! permutations, each n letters to print: time O(n! · n). Space O(n) for the stack. For n = 10 that is 3,628,800 orders.
The library way: next_permutation
next_permutation(s.begin(), s.end()) (from <algorithm>) changes s into the next order in dictionary order (lexicographic order) and returns true; after the last order (cba) it returns false (and puts s back to the first order). So: loop until it returns false.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string s;
cin >> s;
do {
cout << s << " ";
} while (next_permutation(s.begin(), s.end()));
cout << "\n";
return 0;
}
Input cab:
cab cba
Only 2 of 6. It started from the middle of the dictionary (cab) and stopped at the end (cba); abc acb bac bca come before cab and were skipped.
Fix: sort first, so you start at the very first order:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string s;
cin >> s;
sort(s.begin(), s.end()); // start from the FIRST order
do {
cout << s << " ";
} while (next_permutation(s.begin(), s.end()));
cout << "\n";
return 0;
}
Input cab:
abc acb bac bca cab cba
Input aab:
aab aba baa
All six, in dictionary order. With repeated letters, next_permutation prints each different order once: 3 for aab, where the swap version printed 6. Each call is O(n), so the loop is O(n! · n) too, with O(1) extra space.
The recursion tree
The best tool for any recursion question: draw the calls as a tree.
subsets(0)
├─ skip corn → subsets(1)
│ ├─ skip paneer → subsets(2) → skip/take olive → {} {olive}
│ └─ take paneer → subsets(2) → {paneer} {paneer olive}
└─ take corn → subsets(1) → ... 4 more
- Time ≈ number of calls × work per call. Space = the depth of the tree (the calls waiting on the stack), plus any shared data.
- Fast power: 1 call per level, about log₂ b levels (60 for 10^18).
- Calling power twice: 2 calls per level, so 1 + 2 + 4 + ... ≈ 2b calls.
- Subsets: 2 calls per level, n levels: 2^n leaves, 2^(n+1) − 1 calls in all (15 for n = 3).
- Permutations: n calls at the top, n − 1 under each, and so on: n! leaves.
Complexity summary
| Program | Time | Extra space |
|---|---|---|
| a^b, multiply b times | O(b): TLE for 10^18 | O(1) |
a^b, power(a, b/2) * power(a, b/2) |
O(b) calls: TLE | O(log b) |
a^b, fast power, half once |
O(log b) | O(log b) stack |
| a^b, fast power with a loop | O(log b) | O(1) |
| subsets, nested loops | fixed n only: wrong for n ≠ 3 | O(n) |
subsets, skip/take + pop_back |
O(2^n · n) | O(n) |
| subsets, bitmask | O(2^n · n) | O(n) |
| permutations, swap + swap back | O(n! · n) | O(n) |
permutations, sort + next_permutation |
O(n! · n) | O(1) |
When the answer itself has 2^n or n! items, no trick makes it faster: printing them is the work.
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| multiply b times | Time Limit Exceeded | O(b), b = 10^18 | halve b: O(log b) |
power(a, b / 2) * power(a, b / 2) |
31 calls for b = 10, TLE for 10^18 |
two calls per level | half = power(a, b / 2) once |
int half; half * half % MOD |
0 for 2^(10^18), no warning |
int overflow (undefined behaviour) |
long long |
| nested loops for subsets | 8 subsets for 4 toppings |
the number of loops is fixed | recursion, or a bitmask |
take without pop_back() |
{olive paneer olive corn ...} |
the change leaks into the next branch | undo before return |
| swap without the swap back | abc acb cab cba abc acb |
the string is changed under the loop | swap back after the call |
next_permutation without sort |
cab cba (2 of 6) |
starts in the middle of the dictionary | sort first |
| no base case | warning: infinite recursion detected, then TLE or a crash |
the calls never stop | a base case the input reaches |
| recursion 100,000,000 deep | Runtime Error (SIGSEGV) |
the stack overflowed | a loop, or less depth |
The missing base case, exactly as g++ reports it:
main.cpp: In function ‘int place(int)’:
main.cpp:4:5: warning: infinite recursion detected [-Winfinite-recursion]
4 | int place(int n) {
| ^~~~~
main.cpp:5:17: note: recursive call
5 | return place(n - 1) + 1; // no base case: never stops
| ~~~~~^~~~~~~
Your turn: every subset with a bitmask (solution)
Problem. Print every subset without recursion.
Idea. Count a number mask from 0 to 2^n − 1. Bit i of mask says whether item i is in. For n = 3, mask 5 is 101 in binary: bits 0 and 2 are on, so {corn olive}. 1 << n is 2^n, and mask >> i & 1 is bit i.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
vector<string> t(n);
for (auto& s : t) cin >> s;
int cnt = 0;
for (int mask = 0; mask < (1 << n); mask++) { // 0 .. 2^n - 1
cout << "{";
bool first = true;
for (int i = 0; i < n; i++)
if (mask >> i & 1) { // bit i on: item i is IN
cout << (first ? "" : " ") << t[i];
first = false;
}
cout << "} ";
cnt++;
}
cout << "\n" << cnt << " subsets\n";
return 0;
}
Input 3 / corn paneer olive:
{} {corn} {paneer} {corn paneer} {olive} {corn olive} {paneer olive} {corn paneer olive}
8 subsets
Input 4 / corn paneer olive onion:
{} {corn} {paneer} {corn paneer} {olive} {corn olive} {paneer olive} {corn paneer olive} {onion} {corn onion} {paneer onion} {corn paneer onion} {olive onion} {corn olive onion} {paneer olive onion} {corn paneer olive onion}
16 subsets
The same 2^n subsets in a different order (bit 0 changes fastest, so corn flips every step). O(2^n · n) time. 1 << n works while n ≤ 30 for an int; use 1LL << n beyond that (though 2^31 subsets are far too many to print anyway).
Practice questions (with solutions)
1. Every subset with a bitmask. The "your turn" above.
2. Permutations of a string with repeated letters, each once, without next_permutation.
Solution
Sort the string so equal letters sit side by side, and build the answer place by place with a used array. At one place, an equal letter is only used if the copy before it is already in use; otherwise the same order would be built twice.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int cnt = 0;
void perms(const string& s, vector<bool>& used, string& cur) {
if (cur.size() == s.size()) { // base case: every place filled
cout << cur << " ";
cnt++;
return;
}
for (int j = 0; j < (int)s.size(); j++) {
if (used[j]) continue;
// same letter as the one before, and that one is free: this order was already made
if (j > 0 && s[j] == s[j - 1] && !used[j - 1]) continue;
used[j] = true; cur.push_back(s[j]);
perms(s, used, cur);
used[j] = false; cur.pop_back(); // undo
}
}
int main() {
string s;
cin >> s;
sort(s.begin(), s.end()); // equal letters side by side
vector<bool> used(s.size(), false);
string cur;
perms(s, used, cur);
cout << "\n" << cnt << " permutations\n";
return 0;
}
Input aab:
aab aba baa
3 permutations
Input abc:
abc acb bac bca cab cba
6 permutations
Input aabb:
aabb abab abba baab baba bbaa
6 permutations
aabb has 4! / (2! · 2!) = 6 different orders. O(n! · n) time at worst, O(n) space.
3. All strings of n bits with no two 1s next to each other.
Solution
Place one bit per level. A 0 is always allowed; a 1 only at the start or after a 0. Push, recurse, pop: backtracking.
#include <iostream>
#include <string>
using namespace std;
int cnt = 0;
void build(int n, string& cur) {
if ((int)cur.size() == n) { // base case: n bits placed
cout << cur << " ";
cnt++;
return;
}
cur.push_back('0'); // a 0 is always allowed
build(n, cur);
cur.pop_back();
if (cur.empty() || cur.back() == '0') { // a 1 only after a 0 (or at the start)
cur.push_back('1');
build(n, cur);
cur.pop_back();
}
}
int main() {
int n;
cin >> n;
string cur;
build(n, cur);
cout << "\n" << cnt << " strings\n";
return 0;
}
Input 3:
000 001 010 100 101
5 strings
Input 4:
0000 0001 0010 0100 0101 1000 1001 1010
8 strings
The counts 2, 3, 5, 8, 13, ... are the Fibonacci numbers: a string of length n ends in 0 (any valid string of n − 1 bits before it) or in 01 (any valid string of n − 2 bits before it).
4. Fast power without recursion (a loop).
Solution
Read b in binary. 13 = 1101, so a^13 = a^8 · a^4 · a^1. Keep squaring a (a, a^2, a^4, a^8, ...) and multiply it into the answer whenever the current bit of b is 1.
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
long long power(long long a, long long b) {
long long ans = 1;
a %= MOD;
while (b > 0) {
if (b & 1) ans = ans * a % MOD; // this bit of b is 1: use this power of a
a = a * a % MOD; // a, a^2, a^4, a^8, ...
b >>= 1; // next bit
}
return ans;
}
int main() {
long long a, b;
cin >> a >> b;
cout << power(a, b) << "\n";
return 0;
}
Input 2 10:
1024
Input 3 13:
1594323
Input 2 1000000000000000000:
719476260
Input 5 0:
1
O(log b) time, O(1) space: no calls waiting on the stack.
Mini project: the pizza menu planner
The pizza shop wants every pizza a customer can afford. The input is n toppings, the plain pizza's price and the budget, then each topping's name and price. It is the subsets recursion with one extra line: if the cost is already over budget, stop that branch early (adding more toppings only makes it dearer). Cutting off branches that can't lead to an answer is called pruning.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<string> name;
vector<int> price;
int budget, found = 0;
vector<string> cur;
void menu(int i, int cost) {
if (cost > budget) return; // too expensive: stop this branch early
if (i == (int)name.size()) { // base case: every topping decided
cout << "Rs " << cost << ": plain";
for (auto& s : cur) cout << " + " << s;
cout << "\n";
found++;
return;
}
menu(i + 1, cost); // skip topping i
cur.push_back(name[i]); // take topping i
menu(i + 1, cost + price[i]);
cur.pop_back(); // put it back on the shelf
}
int main() {
int n, base;
cin >> n >> base >> budget;
name.resize(n);
price.resize(n);
for (int i = 0; i < n; i++) cin >> name[i] >> price[i];
menu(0, base);
cout << found << " pizzas within Rs " << budget << "\n";
return 0;
}
Input:
4 150 230
corn 30
paneer 60
olive 40
onion 20
Output:
Rs 150: plain
Rs 170: plain + onion
Rs 190: plain + olive
Rs 210: plain + olive + onion
Rs 210: plain + paneer
Rs 230: plain + paneer + onion
Rs 180: plain + corn
Rs 200: plain + corn + onion
Rs 220: plain + corn + olive
9 pizzas within Rs 230
9 of the 16 pizzas fit the budget. cur.pop_back() puts each topping back; without it, every later pizza would carry the old toppings too.
Quick quiz
1. How many calls? (the episode's quiz)
#include <iostream>
using namespace std;
int calls = 0;
int p(int b) {
calls++;
if (b == 0) return 1;
return p(b / 2) * p(b / 2);
}
int main() {
p(8);
cout << calls << "\n";
return 0;
}
(A) 31 (B) 5 (C) 9 (D) 16
Answer
(A) 31. p(b / 2) is called twice per level: 1 call for 8, 2 for 4, 4 for 2, 8 for 1, and 16 for 0. 1 + 2 + 4 + 8 + 16 = 31.
31
With int half = p(b / 2); return half * half; it is only 5:
5
2. What does f(3) print?
#include <iostream>
using namespace std;
void f(int n) {
if (n == 0) return;
cout << n << " ";
f(n - 1);
cout << n << " ";
}
int main() {
f(3);
cout << "\n";
return 0;
}
(A) 3 2 1 (B) 3 2 1 1 2 3 (C) 1 2 3 3 2 1 (D) 3 2 1 0 1 2 3
Answer
(B). Each call prints n on the way down, waits for the smaller call, then prints n again on the way back up. f(0) is the base case and prints nothing.
3 2 1 1 2 3
3. How many times is subsets called for n = 3?
#include <iostream>
using namespace std;
int calls = 0;
void subsets(int i, int n) {
calls++;
if (i == n) return;
subsets(i + 1, n); // skip
subsets(i + 1, n); // take
}
int main() {
subsets(0, 3);
cout << calls << "\n";
return 0;
}
(A) 8 (B) 6 (C) 15 (D) 16
Answer
(C) 15. 1 + 2 + 4 + 8: the 8 leaves (one per subset) plus the 7 calls above them, 2^(n+1) − 1.
15
4. What does this print?
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string s = "bca";
do {
cout << s << " ";
} while (next_permutation(s.begin(), s.end()));
cout << "\n";
return 0;
}
(A) abc acb bac bca cab cba (B) bca cab cba (C) bca (D) bca bac acb abc
Answer
(B). No sort, so it starts at bca and walks forward in dictionary order to the last one, cba.
bca cab cba
Interview questions
- What is recursion? A function that solves a problem by calling itself on a smaller copy of the same problem, with a base case that stops it.
- What happens without a base case? The calls never end: the call stack overflows and the program crashes (g++
-Wallwarnsinfinite recursion detected). - How do you compute a^b mod m fast? Fast power: a^b = (a^(b/2))², times a if b is odd. O(log b).
- Why must
power(a, b/2)be called only once? Calling it twice per level doubles the calls at every level, about 2b calls in all: back to O(b). - Why
long longin fast power? A remainder can be up to 10^9 + 6, and the product of two is about 10^18, too big for anint. Signed overflow is undefined behaviour. - Why 1,000,000,007? It is prime, fits in an
int, and the product of two remainders fits in along long. - How many subsets do n items have? 2^n (each item in or out), including the empty set and the full set.
- What is backtracking? Make a choice, recurse, then undo the choice before trying the next one (
pop_back, swap back). - Time to print all subsets / permutations? O(2^n · n) and O(n! · n): the output itself is that big.
- Subsets without recursion? Count a bitmask from 0 to 2^n − 1; bit i says whether item i is in.
- Why sort before
next_permutation? It moves to the next order in dictionary order and stops after the last one, so starting from an unsorted string skips the orders before it. - Permutations with repeated letters, each once?
sort+next_permutation, or sort and skip an equal letter whose earlier copy is unused. - Recursion or a loop? Recursion is shorter for trees of choices; a loop avoids the stack (O(1) space for fast power) and can't overflow it.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Recursion | A function that calls itself on a smaller copy of the problem | place(n - 1) + 1 |
| Base case | The smallest input, answered directly; it stops the recursion | if (b == 0) return 1; |
| Smaller copy (recursive case) | The call on a smaller input that moves towards the base case | power(a, b / 2) |
| Call stack | The memory where each waiting call keeps its own variables | place(5) waits for place(4) |
| Depth | How many calls wait on the stack at the same time | 61 for fast power with b = 10^18 |
| Stack overflow | Too many waiting calls: the stack runs out and the program crashes | Runtime Error (SIGSEGV) at depth 10^8 |
Modulo (%) |
The remainder after division | 17 % 5 is 2 |
| 1,000,000,007 | 10^9 + 7, the prime used to keep huge answers small | a^b % 1000000007 |
| Modulo rule | (x · y) % m = ((x % m) · (y % m)) % m | take % MOD after every multiply |
| Divide and conquer | Split a problem into smaller ones and build the answer from them | a^b from a^(b/2) |
| Fast power / binary exponentiation | a^b in O(log b) by halving b (or reading its bits) | 61 calls for 2^(10^18) |
| Overflow | A result too big for its type | half * half in int |
| Undefined behaviour | Code the C++ standard gives no meaning to; anything may happen | signed int overflow printed 0 |
int |
A 32-bit integer, up to 2,147,483,647 | about 2 · 10^9 |
long long |
A 64-bit integer, up to about 9.2 · 10^18 | long long half |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | the O(b) loop for b = 10^18 |
| Subset | Some of the items, maybe none, maybe all | {corn olive} |
| Power set | The set of all subsets | 8 subsets of 3 toppings |
| 2^n | The number of subsets of n items | 16 for 4 toppings |
| Skip / take | The two choices for each item in the subsets recursion | skip corn, take corn |
| Backtracking | Try a choice, recurse, undo it, try the next | cur.pop_back() |
| Pruning | Stopping a branch that can't lead to an answer | if (cost > budget) return; |
| Permutation | The same items in a different order | bca is a permutation of abc |
| Factorial (n!) | n × (n − 1) × ... × 1, the number of permutations of n items | 3! = 6 |
| Dictionary / lexicographic order | Ordering strings like words in a dictionary | abc < acb < bac |
next_permutation |
Turns a range into the next lexicographic order; returns false after the last | cab → cba |
sort |
Puts the range in increasing order; the first permutation | cab → abc |
swap |
Exchanges two values | swap(s[i], s[j]) |
| Bitmask | An integer whose bits mark which items are in | 5 = 101 → items 0 and 2 |
1 << n |
1 shifted left n times: 2^n | 1 << 3 is 8 |
mask >> i & 1 |
Bit i of mask (0 or 1) | 5 >> 2 & 1 is 1 |
| Recursion tree | A drawing of every call and the calls it makes | subsets: 2 children per call |
Pass by reference (&) |
The function works on the caller's variable, not a copy | one shared cur |
Summary
- Recursion = a base case + a smaller copy of the same problem. Each call waits on the call stack; too deep, or no base case, and the stack overflows.
- Fast power: a^b = a^(b/2) · a^(b/2) (· a if b is odd). Call
poweronce and keephalf; O(log b). Uselong long:intoverflow is undefined behaviour and printed0. - All subsets: skip or take each item, then
pop_back()to undo the take. O(2^n · n). Or count a bitmask from 0 to 2^n − 1. - All permutations: swap into place, recurse, swap back. O(n! · n). Or
sortfirst, then loopnext_permutation(each order once, even with repeated letters). - Backtracking rule: undo what you did before you return. Test the biggest input too.
Next episode: Backtracking questions: balanced parentheses, combination sum, and the N-Queens puzzle.