Recursion, Backtracking, And Combinatorics
Asked of: Machine Learning Engineer
Last updated
What's being tested
Recursive decomposition, backtracking search, and combinatorial pruning over permutations, expression generation, nested structures, and constrained selections. Interviewers want to see clean state management, duplicate avoidance, complexity reasoning, and when to switch from exhaustive search to binary search, BFS, or dynamic pruning.
Patterns & templates
-
Backtracking template —
dfs(path, used)with choose/recurse/unchoose; permutations costO(n! * n)time andO(n)stack space. -
Duplicate-safe permutations — sort first, then skip
nums[i] == nums[i-1] and not used[i-1]; prevents generating equivalent branches. -
Expression insertion DFS — track
index,value,last_operand, andexpr; multiplication needs undoing previous operand viavalue - last + last * cur. -
Subset/combination pruning —
dfs(start, mask)for character uniqueness; use bitmasks forO(1)overlap checks and early reject invalid strings. -
Nested recursion — compute
depthSum(node, depth)by accumulating integers and recursing into lists; stack depth equals maximum nesting depth. -
Constraint search alternative — shipping capacity is binary search on answer using
canShip(capacity)inO(n log(sum(weights))), not backtracking. -
Grid distance fallback — shortest path in an unweighted grid is BFS,
O(mn)time; recursion risks stack overflow and wrong shortest-path ordering.
Common pitfalls
-
Pitfall: Using a
setof full permutations to remove duplicates works but wastes memory; sort-and-skip is the expected interview solution. -
Pitfall: Forgetting multiplication precedence in expression generation gives plausible but incorrect results; carry
last_operandexplicitly. -
Pitfall: Describing exponential complexity vaguely is weak; state output-sensitive bounds like
O(n! * n)orO(4^n)where applicable.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Solve Three Algorithmic ProblemsMeta · Machine Learning Engineer · Onsite · hard
- Solve shipping capacity and expression insertionMeta · Machine Learning Engineer · Onsite · medium
- Compute nested depth sum and grid distanceMeta · Machine Learning Engineer · Onsite · medium
- Generate unique permutations with duplicatesMeta · Machine Learning Engineer · Onsite · Medium
Related concepts
- Dynamic Programming, Backtracking, And Combinatorial SearchCoding & Algorithms
- Dynamic Programming And Combinatorial CountingCoding & Algorithms
- Trees, Recursion, And BST TraversalCoding & Algorithms
- Binary Tree AlgorithmsCoding & Algorithms
- Dynamic Programming And MemoizationCoding & Algorithms
- Dynamic Programming, Backtracking, and State-Space SearchCoding & Algorithms