Recursion & Backtracking

1.Print 1 to N — Recursion Basics

Print numbers from 1 to n using a recursive function to feel the call stack.

2.Print 1 to N — Induction Way

Frame recursion as mathematical induction: assume f(n-1) works, build f(n).

3.Print 1 to N — Base Cases

Get base cases right: n=0 / n=1 and what happens if you forget them.

4.Print N to 1

Print n down to 1 by printing before the recursive call.

5.Height of a Binary Tree

Height = 1 + max(height(left), height(right)); null height 0.

6.Sort an Array using Recursion

Sort by recursively sorting n-1 elements, then inserting the last into place.

7.Sort a Stack using Recursion

Sort a stack by sorting the remaining stack and inserting the top in sorted order.

8.K-th Symbol in Grammar

Row n is built by replacing 0→01 and 1→10; find the k-th bit (1-indexed).

9.Tower of Hanoi

Move n disks from source to destination using an auxiliary peg.

10.Print All Subsequences

For each element, choose include or exclude; print every subsequence.

11.Print Unique Subsets

Generate all unique subsets when the input may contain duplicates.

12.Permutation with Spaces

Insert spaces between characters in all ways (no leading/trailing space).

13.Permutation with Case Change

For each letter, choose lower or upper case; print all case permutations.

14.Generate Balanced Parentheses

Generate all valid parentheses strings with n pairs.

15.N-bit Binary Numbers with 1s ≥ 0s

Print all n-bit binary strings where in every prefix, count(1) ≥ count(0).

16.Josephus Problem

Every k-th person is eliminated in a circle until one remains.

17.Combination Sum

Combinations that sum to target; reuse allowed.

18.N-Queens

Place n queens with no shared row/col/diag.

19.Sudoku Solver

Backtrack fill empty cells with valid digits.

20.M-Coloring Problem

Color graph vertices with ≤ m colors, no adjacent same.

21.Word Search

DFS on board for a word path (no reuse of cell).