Skip to content

Recursion & Backtracking for Interviews

Does the problem ask for...
├── "All possible combinations/subsets" → Subsets pattern
├── "All possible orderings/arrangements" → Permutations pattern
├── "Ways to make a sum" → Combination Sum pattern
├── "Arrangements with constraints" → Backtracking with pruning
└── "Optimal value (max/min)" → Consider DP (starts with recursion)
function permute(nums) {
const result = [];
const used = new Array(nums.length).fill(false);
function backtrack(current) {
if (current.length === nums.length) {
result.push([...current]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
current.push(nums[i]);
used[i] = true;
backtrack(current);
current.pop();
used[i] = false;
}
}
backtrack([]);
return result;
}
function subsets(nums) {
const result = [];
function backtrack(start, current) {
result.push([...current]);
for (let i = start; i < nums.length; i++) {
current.push(nums[i]);
backtrack(i + 1, current);
current.pop();
}
}
backtrack(0, []);
return result;
}
function combinationSum(candidates, target) {
const result = [];
function backtrack(index, current, remaining) {
if (remaining === 0) {
result.push([...current]);
return;
}
if (remaining < 0 || index >= candidates.length) return;
// Include (can reuse, so pass same index)
current.push(candidates[index]);
backtrack(index, current, remaining - candidates[index]);
current.pop();
// Skip
backtrack(index + 1, current, remaining);
}
backtrack(0, [], target);
return result;
}
ProblemPatternTime ComplexityKey Trick
SubsetsPick/Not-PickO(2ⁿ)Every node is a valid subset
PermutationsUsed arrayO(n!)Track used elements
Combination SumUnlimited reuseO(2^(t/min))Pass i not i+1
Generate ParenthesesOpen/close countsO(4ⁿ/√n)close < open ensures validity
Letter CombinationsMultiple choicesO(4ⁿ)Map digit → letters
Palindrome PartitioningPrefix checkO(n·2ⁿ)Try all palindrome prefixes
  1. Can I sort? Sorting enables better pruning (break instead of continue)
  2. Can I use memoization? Overlapping subproblems? → Cache results
  3. Can I prune? Check early for constraint violations
  4. Can I use iteration? Simple linear recursion → loop is faster

Next: Must-Practice Problems →