Complete search means trying every possible solution and keeping the best one, or counting them. It works for almost any problem, it’s easy to write, and it’s always correct. The only question is whether there’s time. Use the input limits from chapter 2: n ≤ 20 hints at 2ⁿ subsets and n ≤ 10 at n! permutations. When it’s too slow, the rest of the book (greedy, dynamic programming, …) takes over.
Complete search ka matlab: har possible solution try karo, phir best rakho ya sabko gino. Yeh lagbhag har problem pe chalta hai, likhna aasaan hai, aur hamesha sahi answer deta hai — bas sawaal yeh hai ki time hai ya nahi. Chapter 2 ki input limits dekho: n ≤ 20 matlab shayad 2ⁿ subsets, n ≤ 10 matlab n! permutations. Jab yeh slow pade, tab book ka baaki hissa (greedy, dynamic programming, …) kaam aata hai.
5.1Generating subsets
Method 1, recursion: search(k) decides element k. First it leaves k out, then takes it, recursing on k + 1 each time, and k == n means one complete subset. The calls form a binary tree with 2ⁿ leaves, one per subset.
Method 2, bitmasks: each subset of {0, …, n−1} is an n-bit number b. Bit i is 1 exactly when element i is in the subset. Looping b from 0 to 2ⁿ − 1 visits every subset. For example, 25 = 11001₂ means {0, 3, 4}.
Method 1, recursion: search(k) element k ka faisla karta hai — pehle k ko chhodta hai, phir leta hai, aur dono baar k + 1 pe recurse karta hai. k == n matlab ek poora subset ban gaya. Calls ek binary tree banate hain jiske 2ⁿ leaves hain — har subset ke liye ek.
Method 2, bitmasks: {0, …, n−1} ka har subset ek n-bit number b hai: bit i = 1 tabhi jab element i subset mein hai. b ko 0 se 2ⁿ − 1 tak chalao, har subset mil jayega. Jaise 25 = 11001₂ matlab {0, 3, 4}.
static List<Integer> subset = new ArrayList<>(); /** Decide element k: leave it out, then take it. */static void search(int k) { if (k == n) { out.add(new ArrayList<>(subset)); // process subset } else { search(k + 1); subset.add(k); search(k + 1); subset.remove(subset.size() - 1); }}/** Subsets as the bits of b = 0 .. 2^n - 1: bit i set ⇔ element i is in the subset. */static List<List<Integer>> subsetsByBits(int n) { List<List<Integer>> all = new ArrayList<>(); for (int b = 0; b < (1 << n); b++) { List<Integer> s = new ArrayList<>(); for (int i = 0; i < n; i++) { if ((b & (1 << i)) != 0) s.add(i); } all.add(s); } return all;}- current
- path to root
- used in answer
search(0): first leave element 0 OUT (left branch).
static List<Integer> subset = new ArrayList<>(); /** Decide element k: leave it out, then take it. */static void search(int k) { if (k == n) { out.add(new ArrayList<>(subset)); // process subset } else { search(k + 1); subset.add(k); search(k + 1); subset.remove(subset.size() - 1); }}- k
- 0
My notesMere notes
5.2Generating permutations
Method 1, recursion: fill the permutation one position at a time. At each step, try every element not yet chosen, recurse, then undo. This visits all n! permutations in lexicographic order.
Method 2, next permutation: start from the sorted order and repeatedly step to the next permutation. C++ has next_permutation, but Java doesn’t, so here it is:
- Find the longest non-increasing suffix.
- Swap the element just before it with the rightmost larger element.
- Reverse the suffix.
It also handles duplicates correctly, generating each distinct arrangement once.
Method 1, recursion: permutation ek-ek position bharo. Har step pe har woh element try karo jo abhi chosen nahi hai, recurse karo, phir undo. Saare n! permutations lexicographic order mein milte hain.
Method 2, next permutation: sorted order se shuru karo aur baar baar agle permutation pe jao. C++ mein next_permutation hai, Java mein nahi — toh yeh raha:
- Sabse lamba non-increasing suffix dhundho.
- Usse theek pehle wale element ko suffix ke sabse right wale bade element se swap karo.
- Suffix ulta kar do.
Duplicates ko bhi sahi sambhalta hai — har distinct arrangement ek hi baar.
static List<Integer> perm = new ArrayList<>();static boolean[] chosen; static void permute() { if (perm.size() == n) { out.add(new ArrayList<>(perm)); // process permutation return; } for (int i = 0; i < n; i++) { if (chosen[i]) continue; chosen[i] = true; perm.add(i); permute(); chosen[i] = false; perm.remove(perm.size() - 1); }}/** C++'s next_permutation, which Java lacks. Returns false after the last (descending) permutation. */static boolean nextPermutation(int[] a) { int i = a.length - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // longest non-increasing suffix if (i < 0) return false; int j = a.length - 1; while (a[j] <= a[i]) j--; // rightmost element bigger than a[i] int t = a[i]; a[i] = a[j]; a[j] = t; for (int l = i + 1, r = a.length - 1; l < r; l++, r--) { t = a[l]; a[l] = a[r]; a[r] = t; } return true;}My notesMere notes
5.3Backtracking
Backtracking builds a solution step by step and abandons a partial solution as soon as it breaks a rule. Then it undoes the last step and tries the next option.
n queens: count the ways to place n queens on an n × n board so that no two attack each other. Place one queen per row. Three boolean arrays remember which columns and diagonals are taken:
column[x]for each column;diag1[x + y], because x + y is constant along one diagonal direction;diag2[x − y + n − 1], the same for the other direction.
That way each check is O(1). The answers grow fast: q(4) = 2, q(8) = 92, and q(16) = 14,772,512 already takes about a minute.
Backtracking solution ko step by step banata hai, aur jaise hi koi partial solution rule todta hai, use chhod deta hai — aakhri step undo karke agla option try karta hai.
n queens: n × n board pe n queens aise rakho ki koi kisi pe attack na kare — kitne tareeke? Har row mein ek queen. Teen boolean arrays yaad rakhte hain kaunse columns aur diagonals bhare hain:
- har column ke liye
column[x]; diag1[x + y]— ek diagonal direction mein x + y constant rehta hai;diag2[x − y + n − 1]— doosri direction ke liye wahi.
Isliye har check O(1). Answers tezi se badhte hain: q(4) = 2, q(8) = 92, aur q(16) = 14,772,512 mein lagbhag ek minute lag jaata hai.
static int n, count;static boolean[] column, diag1, diag2; // diag1: x + y, diag2: x - y + n - 1 static void search(int y) { if (y == n) { count++; return; } for (int x = 0; x < n; x++) { if (column[x] || diag1[x + y] || diag2[x - y + n - 1]) continue; column[x] = diag1[x + y] = diag2[x - y + n - 1] = true; search(y + 1); column[x] = diag1[x + y] = diag2[x - y + n - 1] = false; }} static int queens(int size) { n = size; count = 0; column = new boolean[n]; diag1 = new boolean[2 * n - 1]; diag2 = new boolean[2 * n - 1]; search(0); return count;}- queen
- safe: placing
- attacked: skip
- attacked square
- just removed
Place one queen per row, top to bottom. Grey squares are attacked by the queens already placed.
static int n, count;static boolean[] column, diag1, diag2; // diag1: x + y, diag2: x - y + n - 1 static void search(int y) { if (y == n) { count++; return; } for (int x = 0; x < n; x++) { if (column[x] || diag1[x + y] || diag2[x - y + n - 1]) continue; column[x] = diag1[x + y] = diag2[x - y + n - 1] = true; search(y + 1); column[x] = diag1[x + y] = diag2[x - y + n - 1] = false; }} static int queens(int size) { n = size; count = 0; column = new boolean[n]; diag1 = new boolean[2 * n - 1]; diag2 = new boolean[2 * n - 1]; search(0); return count;}My notesMere notes
5.4Pruning the search
Pruning adds intelligence: notice as early as possible that a partial solution can’t be completed, and stop exploring it.
The book’s example counts paths through an n × n grid, from the upper-left to the lower-right corner, that visit every square exactly once. A 7 × 7 grid has 111,712 of them. Four simple observations take the search from 483 s to 0.6 s:
- Symmetry: the first move is down or right, and the two cases mirror each other, so explore only “down” and double the count.
- Too early: reaching the corner before visiting everything ends the path, because it can’t be completed.
- Wall split: if a wall blocks the way forward but both left and right are free, the unvisited squares are cut into two parts. Only one can be reached, so stop.
- Any split: the same when the path itself (not just a wall) blocks the way ahead.
Pruning dimaag lagata hai: jitni jaldi ho sake pehchano ki ek partial solution poora nahi ho sakta, aur use explore karna band karo.
Book ka example n × n grid mein upper-left se lower-right corner tak aise paths ginta hai jo har square theek ek baar visit karein — 7 × 7 mein aise 111,712 hain. Chaar simple observations search ko 483 s se 0.6 s tak le aate hain:
- Symmetry: pehla move neeche ya right — dono ek-doosre ka mirror hain, toh sirf “neeche” explore karo aur count double kar do.
- Bahut jaldi: saare squares visit karne se pehle corner pe pahunche toh path wahin khatam — poora ho hi nahi sakta.
- Wall split: aage wall hai par left aur right dono free hain — bache hue squares do hisson mein kat gaye. Ek hi tak pahunch sakte ho, toh ruko.
- Koi bhi split: wahi baat jab aage ka raasta path khud (sirf wall nahi) rok raha ho.
static int n, level;static boolean[][] seen;static long paths, calls;static final int[] DR = {1, 0, -1, 0}, DC = {0, 1, 0, -1}; // down, right, up, left static boolean free(int r, int c) { return r >= 0 && c >= 0 && r < n && c < n && !seen[r][c];} static void search(int r, int c, int visited, int dir) { calls++; if (r == n - 1 && c == n - 1) { if (visited == n * n) { paths++; return; } if (level >= 2) return; } if (level >= 3 && dir >= 0) { int ar = r + DR[dir], ac = c + DC[dir]; boolean wallAhead = ar < 0 || ac < 0 || ar >= n || ac >= n; // Optimisation 3: a wall ahead; optimisation 4: anything blocking ahead (wall or the path). if (level >= 4 ? !free(ar, ac) : wallAhead) { int lf = (dir + 1) % 4, rt = (dir + 3) % 4; // Both sides are free, so the unvisited squares are split in two: give up. if (free(r + DR[lf], c + DC[lf]) && free(r + DR[rt], c + DC[rt])) return; } } for (int d = 0; d < 4; d++) { int nr = r + DR[d], nc = c + DC[d]; if (!free(nr, nc)) continue; seen[nr][nc] = true; search(nr, nc, visited + 1, d); seen[nr][nc] = false; }} static long count(int size, int optimisations) { n = size; level = optimisations; paths = calls = 0; seen = new boolean[n][n]; seen[0][0] = true; if (n == 1) return 1; if (level >= 1) { // Optimisation 1: by symmetry, always step down first and double the answer. seen[1][0] = true; search(1, 0, 2, 0); return 2 * paths; } search(0, 0, 1, -1); return paths;}Count paths from the top-left to the bottom-right square that visit every square once. Each level adds one of the book’s optimisations; all levels must find the same number of paths.
| Level | Paths | Calls | |
|---|---|---|---|
| 0 Basic backtracking | — | — | |
| 1 + symmetry: first step down only, ×2 | — | — | |
| 2 + stop on reaching the corner too early | — | — | |
| 3 + wall ahead, both sides free → split | — | — | |
| 4 + anything ahead, both sides free → split | — | — |
The book’s 7×7 measurements (111,712 paths)
| 0 Basic backtracking | 483 s | 7.6·10¹⁰ calls |
| 1 + symmetry: first step down only, ×2 | 244 s | 3.8·10¹⁰ calls |
| 2 + stop on reaching the corner too early | 119 s | 2.0·10¹⁰ calls |
| 3 + wall ahead, both sides free → split | 1.8 s | 2.2·10⁸ calls |
| 4 + anything ahead, both sides free → split | 0.6 s | 6.9·10⁷ calls |
From 483 s to 0.6 s, about 800× faster, with the same answer. The biggest wins prune near the top of the search tree.
My notesMere notes
5.5Meet in the middle
Meet in the middle splits the search space into two halves, searches each half separately, then combines the results efficiently. It typically turns 2ⁿ into about 2^(n/2): for n = 40, that’s 10⁶ work per half instead of 10¹².
Subset sum: can some numbers of the list add up to x?
- Split the list into A and B.
- List all subset sums S_A and S_B, sorted.
- Ask whether some s_a + s_b = x. Two pointers do it in linear time: start with the smallest of S_A and the largest of S_B, and move whichever side brings the sum closer to x.
For [2, 4, 5, 9] and x = 15: S_A = [0, 2, 4, 6] and S_B = [0, 5, 9, 14], and 6 + 9 = 15, which is the subset {2, 4, 9}.
Meet in the middle search space ko do hisson mein baant-ta hai, dono ko alag search karta hai, phir results ko efficiently jodta hai. Aam taur pe 2ⁿ ko lagbhag 2^(n/2) bana deta hai — n = 40 pe 10¹² ki jagah har half pe 10⁶.
Subset sum: kya list ke kuch numbers ka sum x ban sakta hai?
- List ko A aur B mein todo.
- Saare subset sums S_A aur S_B nikaalo, sorted.
- Poocho: kya koi s_a + s_b = x? Two pointers isse linear time mein karte hain: S_A ke sabse chhote aur S_B ke sabse bade se shuru karo, aur jo side sum ko x ke paas laaye use khiskao.
[2, 4, 5, 9] aur x = 15 ke liye: S_A = [0, 2, 4, 6], S_B = [0, 5, 9, 14], aur 6 + 9 = 15 — yaani subset {2, 4, 9}.
/** All subset sums of a[from..to), sorted. */static long[] subsetSums(long[] a, int from, int to) { int m = to - from; long[] s = new long[1 << m]; for (int b = 0; b < (1 << m); b++) { for (int i = 0; i < m; i++) if ((b & (1 << i)) != 0) s[b] += a[from + i]; } Arrays.sort(s); return s;}static boolean canMake(long[] a, long x) { int half = a.length / 2; long[] sa = subsetSums(a, 0, half); long[] sb = subsetSums(a, half, a.length); int i = 0, j = sb.length - 1; // smallest of SA with the largest of SB while (i < sa.length && j >= 0) { long s = sa[i] + sb[j]; if (s == x) return true; if (s < x) i++; else j--; } return false;}- current
- being read
- used in answer
Can some numbers add up to 15? Trying all 2^4 = 16 subsets works, but split the list in half instead: A and B.
static boolean canMake(long[] a, long x) { int half = a.length / 2; long[] sa = subsetSums(a, 0, half); long[] sb = subsetSums(a, half, a.length); int i = 0, j = sb.length - 1; // smallest of SA with the largest of SB while (i < sa.length && j >= 0) { long s = sa[i] + sb[j]; if (s == x) return true; if (s < x) i++; else j--; } return false;}