Problems

Master recursive problem-solving by tackling these carefully selected problems. Each problem demonstrates different recursive patterns and techniques essential for interviews.

Refer to our Code Templates for reusable patterns.

Easy Problems

1. Climbing Stairs

Brief: Count distinct ways to climb n stairs taking 1 or 2 steps at a time.
Why this pattern?: Each state depends on two previous states, naturally forming a Fibonacci-like recurrence.
Key Insight: Ways to reach step n = ways to reach n-1 + ways to reach n-2.

  graph LR
    subgraph RecursionTree ["Recursion Tree for n=4"]
        N4[4]
        N4 -->|2 steps| N2[2]
        N4 -->|1 step| N3[3]
        N2 --> N0[Base: 1]
        N3 --> N1[Base: 1]
        N2 --> N1
        N3 --> N2

        style N0 fill:#e1ffe1
        style N1 fill:#e1ffe1
    end

Solution

function climbStairs(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n <= 2) return n;

    memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
    return memo[n];
}

from functools import lru_cache

@lru_cache(maxsize=None)
def climbStairs(n):
    if n <= 2:
        return n
    return climbStairs(n - 1) + climbStairs(n - 2)

class Solution {
    private int[] memo;

    public int climbStairs(int n) {
        memo = new int[n + 1];
        return helper(n);
    }

    private int helper(int n) {
        if (n <= 2) return n;
        if (memo[n] != 0) return memo[n];

        memo[n] = helper(n - 1) + helper(n - 2);
        return memo[n];
    }
}

class Solution {
private:
    unordered_map<int, int> memo;
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        if (memo.find(n) != memo.end()) return memo[n];

        memo[n] = climbStairs(n - 1) + climbStairs(n - 2);
        return memo[n];
    }
};

func climbStairs(n int) int {
    memo := make(map[int]int)
    return helper(n, memo)
}

func helper(n int, memo map[int]int) int {
    if n <= 2 {
        return n
    }
    if val, exists := memo[n]; exists {
        return val
    }
    memo[n] = helper(n-1, memo) + helper(n-2, memo)
    return memo[n]
}

def climb_stairs(n, memo = {})
  return n if n <= 2
  return memo[n] if memo.key?(n)

  memo[n] = climb_stairs(n - 1, memo) + climb_stairs(n - 2, memo)
  memo[n]
end

Time:

O(N)

| Space:

O(N)

2. Maximum Depth of Binary Tree

Brief: Find the number of nodes along the longest path from root to farthest leaf.
Why this pattern?: Depth of tree = 1 + max(depth of left subtree, depth of right subtree).
Key Insight: Recurse to find depth of each subtree, then take maximum and add 1 for current node.

  graph TD
    subgraph Tree ["Binary Tree"]
        Root[Root depth=3]
        Root --> Left[Left subtree<br/>depth=2]
        Root --> Right[Right subtree<br/>depth=1]
        Left --> L1[depth=1]
        Left --> L2[depth=0]
        Right --> R1[depth=0]

        style Root fill:#f9d,stroke:#333
    end

Solution

function maxDepth(root) {
    if (!root) return 0;

    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);

    return 1 + Math.max(leftDepth, rightDepth);
}

def maxDepth(root):
    if not root:
        return 0

    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)

    return 1 + max(left_depth, right_depth)

public int maxDepth(TreeNode root) {
    if (root == null) return 0;

    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);

    return 1 + Math.max(leftDepth, rightDepth);
}

int maxDepth(TreeNode* root) {
    if (!root) return 0;

    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);

    return 1 + std::max(leftDepth, rightDepth);
}

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    leftDepth := maxDepth(root.Left)
    rightDepth := maxDepth(root.Right)

    return 1 + max(leftDepth, rightDepth)
}

def max_depth(root)
  return 0 unless root

  left_depth = max_depth(root.left)
  right_depth = max_depth(root.right)

  1 + [left_depth, right_depth].max
end

Time:

O(N)

| Space:

O(H)

(H = height)

Medium Problems

3. Subsets

Brief: Return all possible subsets (power set) of a unique integer array.
Why this pattern?: Each element either included or excluded, generating 2^n combinations.
Key Insight: For each element, recursively explore with it included and without it.

  graph TD
    subgraph Subsets ["Subset Generation for [1,2]"]
        Start[Start]
        Start --> S1[Include 1]
        Start --> S1x[Exclude 1]
        S1 --> S2[Include 2: 1,2]
        S1 --> S2x[Exclude 2: 1]
        S1x --> S2i[Include 2: 2]
        S1x --> S2xi[Exclude 2: ]

        style Start fill:#e1f5ff
    end

Solution

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;
}

def subsets(nums):
    result = []

    def backtrack(start, current):
        result.append(current[:])

        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result

class Solution {
    private List<List<Integer>> result;

    public List<List<Integer>> subsets(int[] nums) {
        result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>());
        return result;
    }

    private void backtrack(int[] nums, int start, List<Integer> current) {
        result.add(new ArrayList<>(current));

        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);
            backtrack(nums, i + 1, current);
            current.remove(current.size() - 1);
        }
    }
}

class Solution {
private:
    vector<vector<int>> result;
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> current;
        backtrack(nums, 0, current);
        return result;
    }

private:
    void backtrack(vector<int>& nums, int start, vector<int>& current) {
        result.push_back(current);

        for (int i = start; i < nums.size(); i++) {
            current.push_back(nums[i]);
            backtrack(nums, i + 1, current);
            current.pop_back();
        }
    }
};

func subsets(nums []int) [][]int {
    var result [][]int
    var current []int
    backtrack(nums, 0, current, &result)
    return result
}

func backtrack(nums []int, start int, current []int, result *[][]int) {
    snapshot := make([]int, len(current))
    copy(snapshot, current)
    *result = append(*result, snapshot)

    for i := start; i < len(nums); i++ {
        current = append(current, nums[i])
        backtrack(nums, i+1, current, result)
        current = current[:len(current)-1]
    }
}

def subsets(nums, start = 0, current = [], result = [])
  result << current.dup

  (start...nums.length).each do |i|
    current << nums[i]
    subsets(nums, i + 1, current, result)
    current.pop
  end

  result
end

Time:

O(2^N)

| Space:

O(2^N)

4. Permutations

Brief: Return all possible orderings of a distinct integer array.
Why this pattern?: Need to generate all n! arrangements by trying each element at each position.
Key Insight: Swap elements to fix each at current position, recurse, then swap back.

  graph TD
    subgraph Permutations ["Permutation Generation for [1,2,3]"]
        Start["Start: [1,2,3]"]
        Start --> P1["Fix 1: [1,2,3]"]
        Start --> P2["Fix 2: [2,1,3]"]
        Start --> P3["Fix 3: [3,2,1]"]
        P1 --> P12["[1,2,3]"]
        P1 --> P13["[1,3,2]"]

        style Start fill:#e1f5ff
    end

Solution

function permute(nums) {
    const result = [];

    function backtrack(start) {
        if (start === nums.length) {
            result.push([...nums]);
            return;
        }

        for (let i = start; i < nums.length; i++) {
            [nums[start], nums[i]] = [nums[i], nums[start]];
            backtrack(start + 1);
            [nums[start], nums[i]] = [nums[i], nums[start]];
        }
    }

    backtrack(0);
    return result;
}

def permute(nums):
    result = []

    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
            return

        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]

    backtrack(0)
    return result

class Solution {
    private List<List<Integer>> result;

    public List<List<Integer>> permute(int[] nums) {
        result = new ArrayList<>();
        backtrack(nums, 0);
        return result;
    }

    private void backtrack(int[] nums, int start) {
        if (start == nums.length) {
            List<Integer> current = new ArrayList<>();
            for (int num : nums) current.add(num);
            result.add(current);
            return;
        }

        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            backtrack(nums, start + 1);
            swap(nums, start, i);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
private:
    vector<vector<int>> result;
public:
    vector<vector<int>> permute(vector<int>& nums) {
        backtrack(nums, 0);
        return result;
    }

private:
    void backtrack(vector<int>& nums, int start) {
        if (start == nums.size()) {
            result.push_back(nums);
            return;
        }

        for (int i = start; i < nums.size(); i++) {
            swap(nums[start], nums[i]);
            backtrack(nums, start + 1);
            swap(nums[start], nums[i]);
        }
    }
};

func permute(nums []int) [][]int {
    var result [][]int
    backtrack(nums, 0, &result)
    return result
}

func backtrack(nums []int, start int, result *[][]int) {
    if start == len(nums) {
        perm := make([]int, len(nums))
        copy(perm, nums)
        *result = append(*result, perm)
        return
    }

    for i := start; i < len(nums); i++ {
        nums[start], nums[i] = nums[i], nums[start]
        backtrack(nums, start+1, result)
        nums[start], nums[i] = nums[i], nums[start]
    }
}

def permute(nums, start = 0, result = [])
  if start == nums.length
    result << nums.dup
    return result
  end

  (start...nums.length).each do |i|
    nums[start], nums[i] = nums[i], nums[start]
    permute(nums, start + 1, result)
    nums[start], nums[i] = nums[i], nums[start]
  end

  result
end

Time:

O(N!)

| Space:

O(N!)

Hard Problems

5. N-Queens

Brief: Place n queens on n×n chessboard so no two attack each other. Return all distinct solutions.
Why this pattern?: Try each position row by row, backtrack when conflict found.
Key Insight: Use arrays to track attacked columns and diagonals for O(1) validation.

  graph TD
    subgraph Board ["4-Queens Board State"]
        Row0["Row 0: Q . . ."]
        Row1["Row 1: . . Q ."]
        Row2["Row 2: . . . Q"]
        Row3["Row 3: . Q . ."]

        Row0 --> Row1
        Row1 --> Row2
        Row2 --> Row3

        style Row0 fill:#f9d,stroke:#333
    end

Solution

function solveNQueens(n) {
    const result = [];
    const board = Array(n).fill().map(() => Array(n).fill('.'));
    const cols = new Set();
    const diag1 = new Set(); // row + col
    const diag2 = new Set(); // row - col

    function backtrack(row) {
        if (row === n) {
            result.push(board.map(row => row.join('')));
            return;
        }

        for (let col = 0; col < n; col++) {
            if (cols.has(col) || diag1.has(row + col) || diag2.has(row - col)) {
                continue;
            }

            board[row][col] = 'Q';
            cols.add(col);
            diag1.add(row + col);
            diag2.add(row - col);

            backtrack(row + 1);

            board[row][col] = '.';
            cols.delete(col);
            diag1.delete(row + col);
            diag2.delete(row - col);
        }
    }

    backtrack(0);
    return result;
}

def solveNQueens(n):
    result = []
    board = [['.' for _ in range(n)] for _ in range(n)]
    cols, diag1, diag2 = set(), set(), set()

    def backtrack(row):
        if row == n:
            result.append([''.join(row) for row in board])
            return

        for col in range(n):
            if col in cols or row + col in diag1 or row - col in diag2:
                continue

            board[row][col] = 'Q'
            cols.add(col)
            diag1.add(row + col)
            diag2.add(row - col)

            backtrack(row + 1)

            board[row][col] = '.'
            cols.remove(col)
            diag1.remove(row + col)
            diag2.remove(row - col)

    backtrack(0)
    return result

class Solution {
    private List<List<String>> result;
    private char[][] board;
    private boolean[] cols, diag1, diag2;
    private int n;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        result = new ArrayList<>();
        board = new char[n][n];
        cols = new boolean[n];
        diag1 = new boolean[2 * n - 1];
        diag2 = new boolean[2 * n - 1];

        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }

        backtrack(0);
        return result;
    }

    private void backtrack(int row) {
        if (row == n) {
            List<String> solution = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                solution.add(new String(board[i]));
            }
            result.add(solution);
            return;
        }

        for (int col = 0; col < n; col++) {
            if (cols[col] || diag1[row + col] || diag2[row - col + n - 1]) {
                continue;
            }

            board[row][col] = 'Q';
            cols[col] = diag1[row + col] = diag2[row - col + n - 1] = true;

            backtrack(row + 1);

            board[row][col] = '.';
            cols[col] = diag1[row + col] = diag2[row - col + n - 1] = false;
        }
    }
}

class Solution {
private:
    vector<vector<string>> result;
    vector<string> board;
    vector<bool> cols, diag1, diag2;
    int n;

public:
    vector<vector<string>> solveNQueens(int n) {
        this->n = n;
        board.assign(n, string(n, '.'));
        cols.assign(n, false);
        diag1.assign(2 * n - 1, false);
        diag2.assign(2 * n - 1, false);
        backtrack(0);
        return result;
    }

private:
    void backtrack(int row) {
        if (row == n) {
            result.push_back(board);
            return;
        }

        for (int col = 0; col < n; col++) {
            if (cols[col] || diag1[row + col] || diag2[row - col + n - 1]) {
                continue;
            }

            board[row][col] = 'Q';
            cols[col] = diag1[row + col] = diag2[row - col + n - 1] = true;

            backtrack(row + 1);

            board[row][col] = '.';
            cols[col] = diag1[row + col] = diag2[row - col + n - 1] = false;
        }
    }
};

func solveNQueens(n int) [][]string {
    var result [][]string
    board := make([][]byte, n)
    for i := range board {
        board[i] = make([]byte, n)
        for j := range board[i] {
            board[i][j] = '.'
        }
    }

    cols := make(map[int]bool)
    diag1 := make(map[int]bool) // row + col
    diag2 := make(map[int]bool) // row - col

    var backtrack func(row int)
    backtrack = func(row int) {
        if row == n {
            solution := make([]string, n)
            for i := range board {
                solution[i] = string(board[i])
            }
            result = append(result, solution)
            return
        }

        for col := 0; col < n; col++ {
            if cols[col] || diag1[row+col] || diag2[row-col] {
                continue
            }

            board[row][col] = 'Q'
            cols[col] = true
            diag1[row+col] = true
            diag2[row-col] = true

            backtrack(row + 1)

            board[row][col] = '.'
            delete(cols, col)
            delete(diag1, row+col)
            delete(diag2, row-col)
        }
    }

    backtrack(0)
    return result
}

def solve_n_queens(n)
  result = []
  board = Array.new(n) { Array.new(n, '.') }
  cols, diag1, diag2 = Set.new, Set.new, Set.new

  backtrack = lambda do |row|
    if row == n
      result << board.map(&:join)
      return
    end

    (0...n).each do |col|
      next if cols.include?(col) || diag1.include?(row + col) || diag2.include?(row - col)

      board[row][col] = 'Q'
      cols << col
      diag1 << (row + col)
      diag2 << (row - col)

      backtrack.call(row + 1)

      board[row][col] = '.'
      cols.delete(col)
      diag1.delete(row + col)
      diag2.delete(row - col)
    end
  end

  backtrack.call(0)
  result
end

Time:

O(N!)

| Space:

O(N^2)

Recommended Study Order

We recommend practicing problems in this sequence to build your recursion skills progressively:

Start with Climbing Stairs - Learn basic recursion with memoization
Move to Maximum Depth - Understand tree recursion patterns
Try Subsets - Master backtracking fundamentals
Progress to Permutations - Learn swap-based backtracking
Challenge with N-Queens - Apply complex constraint satisfaction

This progression teaches you core concepts before tackling complex combinatorial problems.

Pro Tip: Backtracking excels at combinatorial problems. Always ensure proper cleanup when backtracking to avoid bugs.