Question 1

Subsets with a shared path list. Output is a list of empty lists. Why?def dfs(i):
 res.append(path)
 for j in range(i, len(nums)):
 path.append(nums[j]); dfs(j + 1); path.pop()

Accepted Answer

It appends the same list object, so later pops empty every entry res holds references to one list that ends empty. Append path[:] or list(path). Starting from j allows reuse, a different problem. Popping before recursing drops the element. A set cannot hold lists and does not fix aliasing.

Question 2

What is the time to generate all subsets of n distinct items, counting output?

Accepted Answer

O(n 2^n) There are 2^n subsets and copying each costs up to O(n). O(2^n) forgets the copy. O(n^2) is far too small. O(n!) is permutations.

Question 3

Permutations of n distinct integers. How many leaves does the recursion tree have?

Accepted Answer

n! Each level chooses one of the remaining items, so there are n! orderings. 2^n is subsets. n^n allows repeats. n^2 is pairs.

Question 4

Combination Sum: find combinations of candidates that sum to target, unlimited reuse of distinct candidates, combinations must be unique. Which recursive call is right after choosing candidates[j]?

Accepted Answer

dfs(j, remaining - candidates[j]) Passing j allows reuse of the same item while never going back, which keeps combinations unique. j + 1 forbids reuse. 0 produces permutations of the same combination. i + 1 ignores which item was chosen.

Question 5

Subsets II with duplicates in nums. After sorting, which rule in the loop over j from i avoids ever generating a duplicate subset?

Accepted Answer

if j > i and nums[j] == nums[j - 1]: continue Skipping only within the same level (j > i) avoids repeated branches while allowing a duplicate deeper in the path. j > 0 also skips at deeper levels and loses [2, 2]. Checking membership in path loses valid repeats. Final dedupe still generates every duplicate branch first, so it does not avoid generating them.

Question 6

N-Queens (place n queens on an n x n board so no two attack each other): what three sets let you check a placement in O(1)?

Accepted Answer

Columns, diagonals keyed by r - c, and anti diagonals keyed by r + c. Place one queen per row, add to the sets, recurse, then remove on backtrack.

Backtracking coding interview questions

More coding topics

Practise these on your commute