Backtracking Introduction Java | Fresher Interview

All backtracking is recursion, but not all recursion is backtracking, and the difference is what makes this question interesting. Plain recursion typically breaks a problem into subproblems, solves them, and combines the results, like computing factorial or Fibonacci. Backtracking is a specific style of recursion where I build up a candidate solution one choice at a time, and the key idea is that the moment a partial candidate can't possibly lead to a valid complete solution, I abandon it and undo my last choice. The defining pattern is choose, explore, un-choose. I make a choice, I recurse to explore where that choice leads, and then critically I undo the choice, restoring the state so I can try the next option from the same point. That undo step, restoring state after exploring, is the single thing that most distinguishes backtracking from plain recursion, and it's also the thing freshers most often forget, which corrupts the results for the sibling branches. The other distinguishing feature is pruning: before I even explore a branch, I check whether it can lead anywhere valid, and if not, I skip it entirely. Pruning is what keeps backtracking from blindly exploring an exponential search space. Conceptually, I'm walking a decision tree of all possible candidates, going deep, and retreating whenever I hit a dead end. This is the pattern behind permutations, subsets, combinations, N-Queens, Sudoku solvers, and word search. One last tip: when I record a solution, I store a copy of it, not the mutable working list, otherwise later undo operations will mutate what I already saved.