QuizzesBacktracking & Recursion
advanced
dsa

Backtracking & Recursion

Subsets, permutations, combinations, N-Queens, Word Search — master the choose-explore-unchoose pattern.

25 minutes 10 questions Pass at 70%
Time Limit
25 minutes - timer starts when you begin
Change Answers Freely
Revisit and change any answer before submitting
Full Review After Submit
Correct answers and explanations shown for every question
Auto-submit on timeout
Quiz submits automatically when time runs out

Questions in this quiz

10 questions on Backtracking & Recursion. Work through them here, then start the quiz to answer them and see your score.

  1. 1.What is backtracking?

    • AA systematic technique that builds solutions step by step, abandoning partial solutions that cannot lead to a valid answer
    • BA method of undoing commits in version control
    • CA way to reverse a linked list
    • DDynamic programming applied to recursive problems
  2. 2.How many items are in the result list after generating all subsets of [1, 2, 3]?

    public void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path, result);
            path.remove(path.size() - 1); // unchoose
        }
    }
    • A8
    • B7
    • C4
    • D6
  3. 3.What is the "choose-explore-unchoose" pattern in backtracking?

    • ASort the array before recursing
    • BAdd current element to path (choose), recurse into remaining choices (explore), remove it from path (unchoose) — enabling correct exploration of all branches
    • CSelect the first element, recurse on the rest, delete the first element after
    • DA greedy selection strategy for choosing the best element first
  4. 4.What is the time complexity of generating all permutations of n distinct elements?

    • AO(n²)
    • BO(n log n) with backtracking
    • CO(n × n!) — there are n! permutations and each takes O(n) to copy
    • DO(2^n)
  5. 5.In Combination Sum, candidates can be reused. How does backtracking handle this?

    • ABacktracking cannot handle reuse — DP is needed
    • BRecurse with start = i (not i+1) to allow reusing the same element at the same index
    • CUse a used[] array, only marking the first occurrence
    • DSort candidates and track a used[] array
  6. 6.In N-Queens, what is "pruning" and why is it powerful?

    • ARemoving solved queens from the board after finding a solution
    • BImmediately skipping a column if a queen is already in that column, diagonal, or anti-diagonal — without placing or recursing further
    • CSorting the columns before placing queens
    • DChoosing the column with the fewest conflicts first
  7. 7.What does this Word Search DFS + backtracking check?

    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++)
                if (dfs(board, word, i, j, 0)) return true;
        return false;
    }
    // dfs: mark cell visited (e.g. board[i][j] = '#'),
    // explore 4 neighbours for next char,
    // restore cell (backtrack) before returning
    • AWhether all characters in word appear somewhere in the board
    • BWhether the word appears as a contiguous row in the board
    • CWhether the word can be formed using any subset of cells in any order
    • DWhether the word exists as a connected path in the grid where each cell is used at most once per path
  8. 8.What is the time complexity of generating all subsets of an n-element array?

    • AO(n log n)
    • BO(n²)
    • CO(2^n)
    • DO(n!)
  9. 9.Subsets II has duplicate elements (e.g., [1,2,2]). How does backtracking avoid duplicate subsets?

    • ASort first, then skip i > start when nums[i] == nums[i-1] (skip duplicates at the same recursion level)
    • BUse a used[] array for all duplicates
    • CUse a HashSet to de-duplicate results at the end
    • DNever add the same value twice
  10. 10.How does backtracking differ from dynamic programming?

    • ABacktracking explores all possibilities (exponential) with pruning; DP solves overlapping subproblems once and reuses results (polynomial)
    • BBacktracking uses more memory than DP
    • CThey are the same approach with different names
    • DBacktracking is iterative; DP is always recursive