🎯 Top 25 JavaScript Recursion & Backtracking Interview Questions

Parent: Recursion & Backtracking Index

---

Quick Reference

---

Q1. Factorial [E]

Problem: Compute n! recursively.

---

🧠 How to Approach This

Step 1: n! = n × (n-1)! | Base: n <= 1 → return 1

function factorial(n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

console.log(factorial(5));   // 120
console.log(factorial(10));  // 3628800

Time: O(n) | Space: O(n)

---

Q2. Fibonacci (Memoized) [E]

Problem: Return nth Fibonacci number efficiently.

---

🧠 How to Approach This

Step 1: Naive O(2ⁿ) is too slow. Cache with Map for O(n).

function fib(n, memo = new Map()) {
    if (n <= 1) return n;
    if (memo.has(n)) return memo.get(n);
    const result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.set(n, result);
    return result;
}

console.log(fib(10)); // 55
console.log(fib(40)); // 102334155

Time: O(n) | Space: O(n)

---

Q3. Climbing Stairs [E][LC-70]

Problem: Climb n stairs, 1 or 2 steps at a time. How many distinct ways?

---

🧠 How to Approach This

Step 1 — Recognize: This is exactly Fibonacci! ways(n) = ways(n-1) + ways(n-2)

function climbStairs(n, memo = new Map()) {
    if (n <= 2) return n;
    if (memo.has(n)) return memo.get(n);
    const result = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
    memo.set(n, result);
    return result;
}

console.log(climbStairs(2));  // 2
console.log(climbStairs(5));  // 8
console.log(climbStairs(10)); // 89

Time: O(n) | Space: O(n)

---

Q4. Reverse String (In-place Recursive) [E][LC-344]

Problem: Reverse an array of characters in-place using recursion.

---

🧠 How to Approach This

Step 1: Swap first and last, recurse on inner portion.

function reverseString(s, left = 0, right = s.length - 1) {
    if (left >= right) return;
    [s[left], s[right]] = [s[right], s[left]];
    reverseString(s, left + 1, right - 1);
}

const chars = ['h','e','l','l','o'];
reverseString(chars);
console.log(chars.join('')); // "olleh"

Time: O(n) | Space: O(n)

---

Q5. Power Function [M][LC-50]

Problem: Implement pow(x, n) — O(log n).

---

🧠 How to Approach This

Step 1 — Divide & Conquer: x^n = (x^(n/2))² — halve n each step.

function myPow(x, n) {
    if (n === 0)  return 1;
    if (n < 0)    return 1 / myPow(x, -n);
    const half = myPow(x, Math.floor(n / 2));
    return n % 2 === 0 ? half * half : x * half * half;
}

console.log(myPow(2, 10));  // 1024
console.log(myPow(2, -3));  // 0.125

Time: O(log n) | Space: O(log n)

---

Q6. Merge Sort [M]

Problem: Sort array using merge sort.

---

🧠 How to Approach This

Step 1 — Divide: Split in half. Step 2 — Conquer: Merge sorted halves.

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid   = Math.floor(arr.length / 2);
    const left  = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    const res = []; let i = 0, j = 0;
    while (i < left.length && j < right.length)
        res.push(left[i] <= right[j] ? left[i++] : right[j++]);
    return [...res, ...left.slice(i), ...right.slice(j)];
}

console.log(mergeSort([5,2,8,1,9,3])); // [1,2,3,5,8,9]

Time: O(n log n) | Space: O(n)

---

Q7. Binary Search (Recursive) [E]

Problem: Search in sorted array recursively.

---

🧠 How to Approach This

Step 1: mid = (lo+hi)/2. If match → return. If less → search right. Else → search left.

function bSearch(arr, target, lo = 0, hi = arr.length - 1) {
    if (lo > hi) return -1;
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    return target < arr[mid]
        ? bSearch(arr, target, lo, mid - 1)
        : bSearch(arr, target, mid + 1, hi);
}

console.log(bSearch([1,3,5,7,9], 7)); // 3
console.log(bSearch([1,3,5,7,9], 4)); // -1

Time: O(log n) | Space: O(log n)

---

Q8. Generate All Subsets [M][LC-78]

Problem: All subsets of distinct integers.

---

🧠 How to Approach This

Step 1: Include or exclude each element. Push [...current] at base case.

function subsets(nums) {
    const result = [], current = [];
    function bt(i) {
        if (i === nums.length) { result.push([...current]); return; }
        current.push(nums[i]); bt(i + 1);
        current.pop();         bt(i + 1);
    }
    bt(0);
    return result;
}

console.log(subsets([1,2,3]).length); // 8

Time: O(2ⁿ) | Space: O(n)

---

Q9. Generate Permutations [M][LC-46]

Problem: All permutations of distinct integers.

---

🧠 How to Approach This

Step 1: Fix position via swap. After recursion, swap back.

function permute(nums) {
    const result = [];
    function bt(start) {
        if (start === nums.length) { result.push([...nums]); return; }
        for (let j = start; j < nums.length; j++) {
            [nums[start], nums[j]] = [nums[j], nums[start]];
            bt(start + 1);
            [nums[start], nums[j]] = [nums[j], nums[start]];
        }
    }
    bt(0);
    return result;
}

console.log(permute([1,2,3]).length); // 6

Time: O(n × n!) | Space: O(n)

---

Q10. Combination Sum [M][LC-39]

Problem: All combinations summing to target. Reuse allowed.

---

🧠 How to Approach This

Step 1: Sort. At each position: reuse or skip. Break if candidate > remaining.

function combinationSum(candidates, target) {
    candidates.sort((a, b) => a - b);
    const result = [], curr = [];
    function bt(start, rem) {
        if (rem === 0) { result.push([...curr]); return; }
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > rem) break;
            curr.push(candidates[i]);
            bt(i, rem - candidates[i]); // same i — reuse
            curr.pop();
        }
    }
    bt(0, target);
    return result;
}

console.log(combinationSum([2,3,6,7], 7)); // [[2,2,3],[7]]

Time: O(n^(T/M)) | Space: O(T/M)

---

Q11. Subsets II (With Duplicates) [M][LC-90]

Problem: All unique subsets, input may have duplicates.

---

🧠 How to Approach This

Step 1 — Key trick: Sort. Skip nums[i] === nums[i-1] when i > start (same level duplicate).

function subsetsWithDup(nums) {
    nums.sort((a, b) => a - b);
    const result = [], curr = [];
    function bt(start) {
        result.push([...curr]);
        for (let i = start; i < nums.length; i++) {
            if (i > start && nums[i] === nums[i - 1]) continue; // skip dup
            curr.push(nums[i]);
            bt(i + 1);
            curr.pop();
        }
    }
    bt(0);
    return result;
}

console.log(subsetsWithDup([1,2,2]).length); // 6

Time: O(2ⁿ) | Space: O(n)

---

Q12. Permutations II (With Duplicates) [M][LC-47]

Problem: All unique permutations with possible duplicates.

---

🧠 How to Approach This

Step 1 — Key trick: Sort. Use used[] array. Skip if nums[i] == nums[i-1] and used[i-1] is false.

function permuteUnique(nums) {
    nums.sort((a, b) => a - b);
    const result = [], curr = [], used = new Array(nums.length).fill(false);
    function bt() {
        if (curr.length === nums.length) { result.push([...curr]); return; }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] === nums[i-1] && !used[i-1]) continue;
            used[i] = true; curr.push(nums[i]);
            bt();
            curr.pop(); used[i] = false;
        }
    }
    bt();
    return result;
}

console.log(permuteUnique([1,1,2]).length); // 3

Time: O(n × n!) | Space: O(n)

---

Q13. Letter Combinations [M][LC-17]

Problem: All letter combos for a digit string (T9 keyboard).

---

🧠 How to Approach This

Step 1: Map digits to letters. For each digit: try each letter, recurse, backtrack.

function letterCombinations(digits) {
    if (!digits) return [];
    const map = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'};
    const result = [];
    function bt(i, curr) {
        if (i === digits.length) { result.push(curr); return; }
        for (const ch of map[digits[i]]) bt(i + 1, curr + ch);
    }
    bt(0, '');
    return result;
}

console.log(letterCombinations('23').length); // 9

Time: O(4ⁿ × n) | Space: O(n)

---

Q14. Generate Parentheses [M][LC-22]

Problem: All valid combinations of n pairs of parentheses.

---

🧠 How to Approach This

Step 1 — Rules: Add '(' if open < n. Add ')' if close < open. Base: length == 2n.

function generateParenthesis(n) {
    const result = [];
    function bt(curr, open, close) {
        if (curr.length === 2 * n) { result.push(curr); return; }
        if (open < n)     bt(curr + '(', open + 1, close);
        if (close < open) bt(curr + ')', open, close + 1);
    }
    bt('', 0, 0);
    return result;
}

console.log(generateParenthesis(3));
// ["((()))","(()())","(())()","()(())","()()()"]

Time: O(4ⁿ/√n) | Space: O(n)

---

Q15. Palindrome Partitioning [M][LC-131]

Problem: Partition string so every substring is a palindrome. Return all partitions.

---

🧠 How to Approach This

Step 1: Try every prefix. If palindrome → recurse on rest.

function partition(s) {
    const result = [], curr = [];
    const isPalin = str => str === str.split('').reverse().join('');
    function bt(start) {
        if (start === s.length) { result.push([...curr]); return; }
        for (let end = start + 1; end <= s.length; end++) {
            const sub = s.slice(start, end);
            if (isPalin(sub)) {
                curr.push(sub);
                bt(end);
                curr.pop();
            }
        }
    }
    bt(0);
    return result;
}

console.log(partition('aab')); // [["a","a","b"],["aa","b"]]

Time: O(n × 2ⁿ) | Space: O(n)

---

Q16. N-Queens [H][LC-51]

Problem: All solutions for placing n non-attacking queens.

---

🧠 How to Approach This

Step 1: One queen per row. Track cols + diagonals in Sets for O(1) check.

function solveNQueens(n) {
    const result = [], cols = new Set(), d1 = new Set(), d2 = new Set();
    const board = Array.from({length:n}, () => Array(n).fill('.'));
    function bt(row) {
        if (row === n) { result.push(board.map(r => r.join(''))); return; }
        for (let col = 0; col < n; col++) {
            if (cols.has(col) || d1.has(row-col) || d2.has(row+col)) continue;
            board[row][col]='Q'; cols.add(col); d1.add(row-col); d2.add(row+col);
            bt(row + 1);
            board[row][col]='.'; cols.delete(col); d1.delete(row-col); d2.delete(row+col);
        }
    }
    bt(0);
    return result;
}

console.log(solveNQueens(4).length); // 2
console.log(solveNQueens(8).length); // 92

Time: O(n!) | Space: O(n)

---

Q17. Sudoku Solver [H][LC-37]

Problem: Solve a 9×9 Sudoku.

---

🧠 How to Approach This

Step 1: Find empty cell. Try 1-9. Check row/col/box. Recurse. If stuck, restore '.'.

function solveSudoku(board) {
    function isValid(r, c, ch) {
        for (let i = 0; i < 9; i++) {
            if (board[r][i]===ch || board[i][c]===ch) return false;
            const br=Math.floor(r/3)*3+Math.floor(i/3), bc=Math.floor(c/3)*3+i%3;
            if (board[br][bc]===ch) return false;
        }
        return true;
    }
    function solve() {
        for (let r=0;r<9;r++) for (let c=0;c<9;c++) {
            if (board[r][c]!=='.') continue;
            for (let d=1;d<=9;d++) {
                if (isValid(r,c,String(d))) {
                    board[r][c]=String(d);
                    if (solve()) return true;
                    board[r][c]='.';
                }
            }
            return false;
        }
        return true;
    }
    solve();
}

Time: O(9^81) worst | Space: O(1)

---

Q18. Word Search [M][LC-79]

Problem: Does word exist in 2D grid?

---

🧠 How to Approach This

Step 1: DFS from every matching start. Mark '#', explore 4 dirs, restore.

function exist(board, word) {
    const rows = board.length, cols = board[0].length;
    function dfs(r, c, i) {
        if (i===word.length) return true;
        if (r<0||r>=rows||c<0||c>=cols||board[r][c]!==word[i]) return false;
        const tmp=board[r][c]; board[r][c]='#';
        const found=dfs(r+1,c,i+1)||dfs(r-1,c,i+1)||dfs(r,c+1,i+1)||dfs(r,c-1,i+1);
        board[r][c]=tmp;
        return found;
    }
    for (let r=0;r<rows;r++) for (let c=0;c<cols;c++) if (dfs(r,c,0)) return true;
    return false;
}

Time: O(m×n×4^L) | Space: O(L)

---

Q19. Flood Fill [M][LC-733]

Problem: Starting from (sr,sc), replace all connected same-color cells with newColor.

---

🧠 How to Approach This

Step 1: DFS. Change color, recurse on 4 neighbors with original color.

function floodFill(image, sr, sc, color) {
    const orig = image[sr][sc];
    if (orig === color) return image;
    function dfs(r, c) {
        if (r<0||r>=image.length||c<0||c>=image[0].length||image[r][c]!==orig) return;
        image[r][c] = color;
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
    }
    dfs(sr, sc);
    return image;
}

Time: O(m×n) | Space: O(m×n)

---

Q20. Count Paths in Grid [M][LC-62]

Problem: Unique paths from top-left to bottom-right in m×n grid (right/down only).

---

🧠 How to Approach This

Step 1: paths(r,c) = paths(r+1,c) + paths(r,c+1). Base: row or col == 0 → 1. Memoize.

function uniquePaths(m, n, memo = new Map()) {
    if (m === 1 || n === 1) return 1;
    const key = `${m},${n}`;
    if (memo.has(key)) return memo.get(key);
    const result = uniquePaths(m-1,n,memo) + uniquePaths(m,n-1,memo);
    memo.set(key, result);
    return result;
}

console.log(uniquePaths(3, 7)); // 28
console.log(uniquePaths(3, 3)); // 6

Time: O(m×n) | Space: O(m×n)

---

Q21. Decode Ways [M][LC-91]

Problem: Count ways to decode a digit string into letters (1=A, 26=Z).

---

🧠 How to Approach This

Step 1 — Choices: Decode 1 digit OR 2 digits. Prune '0' starts and values > 26.

function numDecodings(s, i = 0, memo = new Map()) {
    if (i === s.length) return 1;
    if (s[i] === '0')   return 0;
    if (memo.has(i))    return memo.get(i);

    let ways = numDecodings(s, i + 1, memo);

    if (i + 1 < s.length) {
        const two = parseInt(s.slice(i, i + 2));
        if (two >= 10 && two <= 26)
            ways += numDecodings(s, i + 2, memo);
    }

    memo.set(i, ways);
    return ways;
}

console.log(numDecodings('226'));  // 3
console.log(numDecodings('06'));   // 0

Time: O(n) | Space: O(n)

---

Q22. Restore IP Addresses [M][LC-93]

Problem: All valid IPv4 addresses from a digit string.

---

🧠 How to Approach This

Step 1 — 4 parts, each 0-255, no leading zeros. Backtrack with depth limit of 4.

function restoreIpAddresses(s) {
    const result = [], parts = [];
    function bt(start) {
        if (parts.length===4 && start===s.length) { result.push(parts.join('.')); return; }
        if (parts.length===4 || start===s.length) return;
        for (let len=1; len<=3; len++) {
            if (start+len>s.length) break;
            const seg=s.slice(start,start+len);
            if (len>1 && seg[0]==='0') break;
            if (parseInt(seg)>255) break;
            parts.push(seg); bt(start+len); parts.pop();
        }
    }
    bt(0);
    return result;
}

console.log(restoreIpAddresses('25525511135'));
// ["255.255.11.135","255.255.111.35"]

Time: O(1) bounded | Space: O(1)

---

Q23. Word Break [M][LC-139]

Problem: Can the string be segmented into dictionary words?

---

🧠 How to Approach This

Step 1: Try every prefix. If it's in dict, recurse on rest. Memoize by start index.

function wordBreak(s, wordDict, start = 0, memo = new Map()) {
    if (start === s.length) return true;
    if (memo.has(start))    return memo.get(start);

    const words = new Set(wordDict);
    for (let end = start + 1; end <= s.length; end++) {
        if (words.has(s.slice(start, end)) && wordBreak(s, wordDict, end, memo)) {
            memo.set(start, true);
            return true;
        }
    }
    memo.set(start, false);
    return false;
}

console.log(wordBreak('leetcode', ['leet','code']));      // true
console.log(wordBreak('applepenapple', ['apple','pen'])); // true

Time: O(n²) | Space: O(n)

---

Q24. Tower of Hanoi [M]

Problem: Print moves to move n disks from A to C using B.

function hanoi(n, from, to, via) {
    if (n === 1) { console.log(`Move disk 1: ${from} → ${to}`); return; }
    hanoi(n - 1, from, via, to);
    console.log(`Move disk ${n}: ${from} → ${to}`);
    hanoi(n - 1, via, to, from);
}
hanoi(3, 'A', 'C', 'B');

Time: O(2ⁿ) | Space: O(n)

---

Q25. Target Sum [M][LC-494]

Problem: Assign '+' or '-' to each number. Count ways to reach target sum.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

At each position: add or subtract. Two branches → 2ⁿ paths total. Memoize (index, currentSum).

Step 2 — Memoization key: ${index},${sum}

function findTargetSumWays(nums, target, idx = 0, curr = 0, memo = new Map()) {
    if (idx === nums.length) return curr === target ? 1 : 0;

    const key = `${idx},${curr}`;
    if (memo.has(key)) return memo.get(key);

    const add = findTargetSumWays(nums, target, idx + 1, curr + nums[idx], memo);
    const sub = findTargetSumWays(nums, target, idx + 1, curr - nums[idx], memo);

    memo.set(key, add + sub);
    return add + sub;
}

console.log(findTargetSumWays([1,1,1,1,1], 3)); // 5
console.log(findTargetSumWays([1], 1));           // 1

Time: O(n × sum) | Space: O(n × sum)

---

Summary: Backtracking Decision Guide