Backtracking
Last updated
Was this helpful?
Last updated
Was this helpful?
Use cases:
Output all results. This must be backtracking, at most with memorization.
Find how many ways to do xyz. DP, a typical DFS + memorization pattern.
One important idea of Backtracking is modify -> restore
, like this one is different from traditional add, remove
List: , tmp = board[r][c]; -> board[r][c] = '#'; -> board[r][c] = tmp;
Duplicate: 1) sort array/list first; 2) skip duplicate at each level by if (visiting[i] || i > 0 && nums[i] == nums[i-1] && !visiting[i-1]) continue;
Have a boolean[] visiting
to marked points visited, avoid duplicate
Duplicate: 1) sort array/list first; 2) skip duplicate at each level by if (i > start && candidates[i] == candidates[i-1]) continue;
Don't need to have visited set or boolean array
These are more of a DP:
(This is more of a permutation where you can use an element repeatedly.)
one common type is add -> remove. the other type is like drawing a tree, enumerate possible solutions