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