DEV Community

DevCorner2
DevCorner2

Posted on

🚀 Blog 8: Backtracking & Recursion — Expedia DSA Prep

Expedia often asks constraint-based exploration problems that require:

  • Generating subsets/permutations
  • Placing constraints (N-Queens, Sudoku)
  • Searching grids (Word Search, Rat in Maze)

We’ll cover:

  1. Subsets (Power Set)
  2. Word Search in Grid
  3. N-Queens

🔹 Problem 1: Subsets (Power Set)

Pattern: Backtracking with include/exclude

📌 Given an array nums, return all possible subsets.

import java.util.*;

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

    private static void backtrack(List<List<Integer>> res, List<Integer> temp, int[] nums, int start) {
        res.add(new ArrayList<>(temp));
        for (int i = start; i < nums.length; i++) {
            temp.add(nums[i]);
            backtrack(res, temp, nums, i + 1);
            temp.remove(temp.size() - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1,2,3}));
        // [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Time Complexity: O(2^N)

🔹 Problem 2: Word Search in Grid

Pattern: DFS Backtracking

📌 Given a 2D board and a word, check if the word exists in the grid.

public class WordSearch {
    public static boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }

    private static boolean dfs(char[][] board, String word, int i, int j, int idx) {
        if (idx == word.length()) return true;
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != word.charAt(idx)) 
            return false;

        char temp = board[i][j];
        board[i][j] = '#'; // mark visited

        boolean found = dfs(board, word, i + 1, j, idx + 1) ||
                        dfs(board, word, i - 1, j, idx + 1) ||
                        dfs(board, word, i, j + 1, idx + 1) ||
                        dfs(board, word, i, j - 1, idx + 1);

        board[i][j] = temp; // backtrack
        return found;
    }

    public static void main(String[] args) {
        char[][] board = {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        };
        System.out.println(exist(board, "ABCCED")); // true
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Time Complexity: O(M × N × 4^L), where L = word length

🔹 Problem 3: N-Queens

Pattern: Backtracking with constraints

📌 Place N queens on an N×N chessboard such that no two queens attack each other.

import java.util.*;

public class NQueens {
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(res, board, 0);
        return res;
    }

    private static void backtrack(List<List<String>> res, char[][] board, int row) {
        if (row == board.length) {
            res.add(construct(board));
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(res, board, row + 1);
                board[row][col] = '.';
            }
        }
    }

    private static boolean isValid(char[][] board, int row, int col) {
        for (int i = 0; i < row; i++) 
            if (board[i][col] == 'Q') return false;

        for (int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--)
            if (board[i][j] == 'Q') return false;

        for (int i = row-1, j = col+1; i >= 0 && j < board.length; i--, j++)
            if (board[i][j] == 'Q') return false;

        return true;
    }

    private static List<String> construct(char[][] board) {
        List<String> list = new ArrayList<>();
        for (char[] row : board) list.add(new String(row));
        return list;
    }

    public static void main(String[] args) {
        System.out.println(solveNQueens(4));
        // [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Time Complexity: O(N!)

📊 Expedia Backtracking Key Insights

  • Subsets/Permutations → pure recursive exploration.
  • Grid search → DFS with marking/unmarking.
  • Constraint problems (N-Queens, Sudoku) → prune invalid choices early.

👉 In Blog 9, we’ll transition into Dynamic Programming (DP) — another must-master pattern for Expedia, covering classics like House Robber, Coin Change, Longest Increasing Subsequence.

Top comments (0)