Bird
Raised Fist0

What is the subtle bug?

medium🐞 Bug Identification Q7 of Q15
Topological Sort - All Paths From Source to Target (DAG)
Examine the following DFS code snippet for finding all paths from source to target in a DAG. What is the subtle bug? ```python def dfs(node, path): if node == target: res.append(path) return for nei in graph[node]: path.append(nei) dfs(nei, path) path.pop() ```
AMissing base case for target node.
BAppending path directly to results without copying.
CUsing iterative DFS instead of recursive.
DNot backtracking path after recursion, causing path corruption.
Step-by-Step Solution
Solution:
  1. Step 1: Trace path modifications

    Path is appended with neighbor before recursion but never popped after, so path grows incorrectly.
  2. Step 2: Identify missing backtracking

    Backtracking requires popping the last node after recursive call to restore path state.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Without backtracking, paths accumulate extra nodes [OK]
Quick Trick: Always backtrack path after recursion [OK]
Common Mistakes:
MISTAKES
  • Forgetting to pop after recursion
  • Assuming path copies happen automatically
Trap Explanation:
PITFALL
  • Candidates often miss the need to backtrack path state, causing incorrect path accumulation.
Interviewer Note:
CONTEXT
  • Tests candidate's understanding of backtracking mechanics in DFS.
Master "All Paths From Source to Target (DAG)" in Topological Sort

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Topological Sort Quizzes