In an interview, an NP-hard problem never means “find a polynomial algorithm”. It means: find the parameter that is small, and exploit it. That takes two skills. The first is telling a hard problem from an easy one that looks almost the same — one changed word often moves a problem across the line. The second is reading the constraints: n ≤ 20, n ≤ 40, values up to 104 each point at a specific technique. This page covers both, with C++ for every technique, tested against brute force. The graph algorithms it leans on have their own page, graph algorithms, step by step, and so do the everyday DPs: dynamic programming, step by step.
Four words, and only one fact that matters at the whiteboard: for NP-hard problems nobody knows an algorithm that is polynomial in the input size, and finding one would be the most famous result in computer science.
Whether P = NP has been open since Stephen Cook's 1971 paper, and a proof either way is worth a $1M Clay Millennium Prize. Almost everyone believes P ≠ NP, and so does this page.
To show your problem X is hard, translate a known hard problem into X: “if I could solve X fast, I could solve Hamiltonian path fast.” The other direction proves nothing. Translating X into SAT only shows X is no harder than SAT — sorting can be written as SAT too.
Assuming P ≠ NP. NP-complete is where NP and NP-hard overlap. If P = NP, the three regions inside NP merge into one.
Interview problems never say NP-hard. They tell a story — teams, cookies, stickers, delivery routes — around one of six shapes. Strip the story, find the shape, then read the constraints for the way out.
sounds likesplit into two equal halves · put + or − before every number · smash stones until one is left · fill a bag without going over
underneathsubset sum, partition, 0/1 knapsack
way outsmall values → DP over sums · n ≤ 40 → meet in the middle
sounds likevisit all nodes · the shortest string containing every word · walk over every empty cell once · order items so that every neighbor pair fits · the longest path that repeats nothing
underneathHamiltonian path, traveling salesman, longest simple path
way outn ≤ 20 → bitmask DP over (visited set, last) · small grids → backtracking
sounds likethe smallest team that has every skill · the fewest stickers that spell a word · the fewest cameras, guards or stations that watch everything
underneathset cover, vertex cover, dominating set
way outfew things to cover (≤ 16 skills) → bitmask DP over what is covered · a tree → tree DP · huge → greedy, ln n
sounds likematchsticks into a square · jobs to k workers, busiest one done first · the fewest work sessions · cookies to children as fairly as possible
underneathbin packing, multiway partition, makespan scheduling
way outbacktracking that prunes · DP over submasks, 3n
sounds likeseat students so nobody can copy · rob houses that aren't neighbors · the biggest group where everyone knows everyone · exam slots so nobody has two at once
underneathindependent set, clique, graph coloring
way outnarrow grid → row-by-row bitmask DP · a tree → tree DP · intervals → greedy
sounds likefill in the Sudoku · place N queens · assign values so every rule holds
underneathSAT, exact cover, constraint satisfaction
way outbacktracking: fill the most constrained spot first, check every rule before recursing. A 9×9 board is small; the general n2×n2 Sudoku is NP-complete.
The 20-second test. Before you say NP-hard, write down the state a DP would need and count how many values it can take. Positions, prefixes, pairs (i, j), a node plus a flag: polynomially many, so the problem is probably in P. “Which items have I used so far”: 2n values — hard territory, and the hunt for a small parameter begins.
Most hard problems have an easy twin: edge instead of node, two instead of three, contiguous instead of any. Calling an easy problem NP-hard looks worse in an interview than the reverse, so it pays to know the pairs. Test yourself, then check the table.
| polynomial | NP-hard | what changes |
|---|---|---|
| Use every edge exactly onceEuler path · step by step | Visit every node exactly onceHamiltonian path | Degrees, plus one connectivity check, settle Euler. Whether a partial Hamiltonian path can still be finished depends on the whole set of nodes it has used. |
| Connect every city as cheaply as possibleminimum spanning tree · step by step | Visit every city and come back, as cheaply as possibletraveling salesman | Choosing edges versus choosing an order. The cut property lets greedy commit to an edge; nothing lets you commit to one leg of a tour. |
| Connect every cityminimum spanning tree | Connect only the marked cities, through any of the othersSteiner tree | Which unmarked cities to route through is a subset choice. |
| Color the nodes with 2 colors so no edge joins two of the samebipartite check · BFS | The same with 3 colors3-coloring | With two colors every choice is forced by a neighbor. With three, choices stay open and interact across the graph. |
| Shortest path between two nodes, no negative cyclesDijkstra, Bellman–Ford | Longest path that repeats no nodelongest simple path | A shortest path never wants to revisit a node, so “no repeats” comes free. A longest one always would, so it becomes a global constraint. |
| Longest path in a graph with no cyclesDAG · topological order + DP | Longest path in a graph with cycleslongest simple path | The topological order gives the DP an order to fill in. Cycles take it away. |
| Pair workers with jobs they can do, as many pairs as possiblebipartite matching | Group workers, jobs and machines into compatible triples3-dimensional matching | An augmenting path improves a matching one pair at a time. Triples have no such move. |
| Fewest edges that touch every nodeedge cover | Fewest nodes that touch every edgevertex cover | Edge cover = n − maximum matching. Vertex cover has no such formula, except in bipartite graphs, where König's theorem makes it a matching too. |
| Most intervals with no two overlappinginterval scheduling | Most nodes with no edge between any twomaximum independent set | On a line, the interval that ends first is always a safe pick. A general graph has no such order. |
| Fewest rooms for a set of meetingscoloring intervals | Fewest colors for any graphchromatic number | For intervals the answer is the largest overlap at a single moment, found by one sweep. |
| Split an array into two contiguous parts with equal sumsprefix sums | Split it into two subsets with equal sumspartition | Contiguous: n − 1 places to cut. Subsets: 2n ways to choose. |
| Fill a bag when items can be cut into piecesfractional knapsack | Fill a bag with whole items0/1 knapsack | Cutting lets greedy go by value per weight. Whole items need a DP over capacity, which is only pseudo-polynomial. |
| Unit-time jobs with deadlines and profits, most profitgreedy + union-find | Jobs of any length with deadlines and weights, least weight lateweighted late jobs | Equal lengths make jobs interchangeable, so greedy by profit is safe (a matroid). Different lengths turn it into knapsack. |
| Satisfy clauses of two literals each, like (a or not b)2-SAT | Satisfy clauses of three literals each3-SAT | A two-literal clause is two implications; strongly connected components of the implication graph decide it. |
| Drive down every street, as short as possibleChinese postman | Stop at every house, as short as possibletraveling salesman | Streets are edges again: Euler's degree test, plus a matching that pairs up the odd-degree corners. |
| Optimize a linear objective over real numberslinear programming | The same, with whole numbers onlyinteger linear programming | Real solutions form one convex region, where a local optimum is global. Requiring integers breaks it into separate points. |
Drag the cities. On the left, the cheapest network that connects them all: Kruskal and Prim decide one edge at a time, on its own merits, so this scales to millions of cities. On the right, the cheapest round trip, found with the 2n·n2 DP from the playbook — which is why this demo stops at 12 cities. The dashed tour walks around the tree and skips cities it has seen. It is never longer than twice the tree, and the tree is never longer than the best tour (remove one leg of a tour and you have a spanning tree), so the walk is within 2× of optimal.
At 60 cities, Kruskal sorts 1,770 edges. There are 6.9 × 1079 different round trips, and even the DP needs 4.2 × 1021 steps.
Every polynomial problem in the table escapes through one of four hatches. Before calling a problem hard, look for each of them. If none is there, it probably is hard.
A DP needs each subproblem finished before it is used. A topological order provides that in a DAG; so do children-before-parents in a tree, left-to-right along a timeline, and positions in a string. Cycles take the order away, which is exactly why longest path is easy in a DAG and hard in general.
LC 329 Longest Increasing Path in a Matrix · 337 House Robber III · 139 Word Break · 1235 Maximum Profit in Job Scheduling
When every decision is forced by an earlier one, there is nothing to search. With two colors, one node's color fixes its neighbors', and theirs, all the way out: a BFS. In 2-SAT every clause is a pair of implications. With three colors, the choices stay open, and they interact.
LC 785 Is Graph Bipartite? · 886 Possible Bipartition
If any optimal answer can be rearranged to include the greedy choice without getting worse, greedy is safe. That is the cut property for spanning trees (Kruskal, Prim), closest-first for Dijkstra with weights ≥ 0, and earliest-ending interval first. Try the same swap on TSP or 0/1 knapsack and it fails — and so does greedy.
LC 435 Non-overlapping Intervals · 1584 Min Cost to Connect All Points · 630 Course Schedule III
Matching and flow improve one step at a time: while an improving path exists, take it; when none is left, the answer is optimal (Berge's theorem for matchings, max-flow = min-cut for flows). That covers pairing workers with jobs, minimum cuts, and edge cover. Triples have no improving paths.
LC 1820 Maximum Number of Accepted Invitations · 1066 Campus Bikes II (small n: bitmask DP is expected)
The hard side has none of the four. You are choosing a subset or an order, and every choice constrains every other one.
A judge runs roughly 108 simple C++ operations a second. Polynomial curves stay far under that line for any n you will be given; exponential ones hit it at a definite n — and that n is the constraint printed in the problem. n ≤ 20 means 2n is expected. n ≤ 40 means 2n/2, done twice: meet in the middle.
| growth | typical use | max n in 1 s |
|---|---|---|
| n log n | sorting, heaps, Dijkstra | ≈ 4.5 million |
| n2 | DP over pairs (i, j) | 10,000 |
| n3 | Floyd–Warshall, interval DP | ≈ 460 |
| 2n/2·n | meet in the middle | ≈ 42 |
| 2n | every subset | ≈ 26 |
| 2n·n | bitmask DP, one item per step | ≈ 22 |
| 2n·n2 | bitmask DP with a last node: TSP | ≈ 18 |
| 3n | DP over submasks | ≈ 16 |
| n! | every order | ≈ 11 |
108 a second is a rule of thumb, good to a factor of 3 or so: tight loops over arrays and bits run faster, hash maps and allocations slower. Setters leave room, so expect n ≤ 20 for 2n·n and n ≤ 12–16 for 2n·n2 or 3n.
Once you have said “this is NP-hard”, the next sentence names the small parameter. Ask for the constraints before anything else: they are the setter's hint.
| what is small | reach for | cost |
|---|---|---|
| n ≤ 10 or 11 | try every order: next_permutation | O(n!·n) |
| n ≤ 20 | bitmask DP over subsets | O(2n·n) to O(2n·n2) |
| n ≤ 15, split into groups | DP over submasks | O(k·3n) |
| n ≤ 40 | meet in the middle | O(2n/2·n) |
| the values: sums up to ~106 | DP over sums | O(n·S) |
| the answer k | branch on a forced choice | O(2k·E) |
| nothing, but any valid answer will do | backtracking that prunes | exponential, often fast |
| the structure: tree, DAG, intervals, bipartite | the special case's algorithm | polynomial |
| nothing, and n is huge | an approximation with a known ratio | polynomial |
Brute force tries all n! orders. But to extend a partial tour you only need to know which cities it has visited and where it stands now — not the order it took. So the state is (mask, last): 2n·n states, n ways out of each, O(2n·n2) in total. At n = 15 that is 7.4·106 steps instead of 1.3·1012.
mask >> i & 1 asks whether i is in the set, mask | 1 << i adds it, __builtin_popcount(mask) counts it.long long. Use int when the distances allow.dp[mask], O(2n·n).When the answer splits the items into groups — workers, sessions, children — let dp[mask] be the best answer for exactly the items in mask, and let the newest group take any submask of it. The loop for (sub = mask; sub; sub = (sub - 1) & mask) visits every nonempty submask exactly once.
Summed over all masks that is 3n, not 4n: each item is either in sub, in mask but not in sub, or outside mask. With k groups the program below costs O(k·3n), fine up to n ≈ 15 (315 = 1.4·107).
Precompute what each group costs (load[mask]) once, in O(2n), by peeling off the lowest set bit.
240 ≈ 1012 subsets is far too many; 2 × 220 ≈ 2·106 is not. Split the items into two halves and list every subset sum of each. A subset of everything is a subset of the left half plus a subset of the right, so sort one list, and for each sum x in the other, binary-search the partner closest to goal − x. O(2n/2·n) time, O(2n/2) memory.
It works whenever an answer splits into two independent halves that combine through a sort or a hash map: sums, XORs, counts of ways.
Subset sum is NP-complete, yet O(n·S) solves it, where S is the target. No contradiction: S is a number written in about log2 S bits, so n·S is exponential in the length of the input. Algorithms like this are called pseudo-polynomial, and only weakly NP-hard problems have them — the knapsack family. TSP, bin packing and 3-partition are strongly NP-hard: no DP over numbers helps. Say this sentence in the interview; it is the difference between “I memorized a DP” and “I know why it works”. The same table, filled in step by step: 0/1 knapsack and coin change.
With a bitset each item costs one shift and one OR over S bits. Step through it:
dp[i][j]. Still pseudo-polynomial.If the question is whether at most k picks suffice, and k is small, look for something that forces a choice. Every uncovered edge needs one of its two ends in a vertex cover, so branch on both: the search tree is at most k deep with at most 2k leaves.
O(2k·E) is exponential in k only: k = 10 with 100,000 edges is about 108 steps, while trying every set of 10 nodes out of 10,000 would take about 1033. Problems like this are called fixed-parameter tractable. Interviews rarely ask for one by name, but the idea — put the exponential cost on the parameter that is small — is exactly what the interviewer is listening for.
When no parameter is small but any valid answer will do, search — and spend the effort on cutting branches early. The grade is in the pruning:
Many NP-hard graph problems are easy on special graphs, so check whether the input really is a general graph. Independent set, vertex cover and dominating set are linear on trees: finish the children before the parent and keep two answers per node, with it and without it.
Likewise longest path is linear in a DAG (topological order), coloring intervals takes one sweep, and in a bipartite graph the smallest vertex cover is as big as the largest matching.
With n = 105 and no structure, exact is off the table. Say so, then offer an algorithm with a proven ratio. Knowing a few by heart is a senior signal:
No guarantee needed? Local search, simulated annealing and random restarts are the practical fallback.
The order to say things in, so the interviewer hears the reasoning and not only the code.
LC 1723, k workers, n ≤ 12 jobs — out loud:
“Splitting jobs between workers to minimize the busiest one is makespan scheduling, which is NP-hard, so I won't look for a polynomial exact solution.
n is at most 12, so a set of jobs fits in a bitmask. I'll precompute the total time of every subset, then go worker by worker: dp[mask] is the best finishing time when the workers so far have exactly the jobs in mask, and the next worker takes some submask. That's O(k·3n), about 6·106 for n = 12.
If n were 105, I'd sort the jobs from longest to shortest and give each to the least loaded worker: within 4/3 of optimal.”