Interview Q&A / Data Structures & Algorithms

1. How do you generate all permutations of an array using backtracking?

   Build the permutation one position at a time. Try every unused element at the current position, mark it used, recurse, then unmark it. A complete path of length n is one permutation; there are n! of them.

   IntermediateQuick answerCoding1 min read
2. How do you generate all subsets of an array using backtracking?

   At each step, record the current path as a subset, then try adding each remaining element, recurse, and remove it again. An array of n items has 2^n subsets.

   IntermediateQuick answerCoding1 min read
3. How do you generate all valid combinations of n pairs of parentheses?

   Build the string character by character. You may add an opening bracket while fewer than n have been used, and a closing bracket only when it would not exceed the number of openings. A string of length 2n is valid.

   IntermediateQuick answerCoding1 min read
4. How do you solve Combination Sum, finding all combinations that add up to a target when numbers can be reused?

   Sort the candidates and backtrack with a start index. Add a candidate, recurse with the reduced target (same start index so it can be reused), and stop a branch when the target is zero or the candidate exceeds it.

   IntermediateQuick answerCoding1 min read
5. How do you solve the N-Queens problem with backtracking?

   Place one queen per row. For each column in the row, check that no earlier queen shares the column or a diagonal. If safe, place it and recurse to the next row; otherwise skip. Undo and try the next column.

   AdvancedQuick answerCoding1 min read