Backtracking & Recursion
Subsets, permutations, combinations, N-Queens, Word Search — master the choose-explore-unchoose pattern.
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.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.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.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.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.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.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.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.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.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.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