In fact, backtracking is exhaustive method.
Therefore, those problems exist the pattern which can be solved by DFS.
Solutions can be construct a tree, then using DFS to list all effect answers.
Mental cultivation:
1. Looks like DFS.
Start from the root.
Traverse and create a list to note the tracked node.
Check the node belong to answers or not.
If not, give up the sub-tree which root is this node.
If yes, add into answer pool and keep searching.
2. If tracking the sub-tree is ready,
in order to track back to the last node,
remember to remove this node (the root of this sub-tree) from the noted list.
Examples:
- N-Queens
- N-Queens II
- Combination Sum
- Combination Sum II
- Combination Sum III
- Permutations
- Permutations II
- Subsets
- Subsets II
- Palindrome Partitioning
Template:
// vector selected will collect the choosen numbers,
// nums is the original input
// pos is the choosen index
// len = nums.size() is the lenth of nums
void helper(vector& nums, vector& selected, int pos, int len){
// end condition
if(……){
……
return;
}
// traverse all of nums
for(int i = 0; i < len;i++){
int val = nums[i];
// if val has been choosen, igore
if(find(selected.begin(), selected.end(), val) != selected.end()){
continue;
}
// choose a numner val
selected.push_back(val);
// next traverse,pos+1
helper(nums, selected, pos + 1, len);
// because the node has been traverse its subtree,
// remove from selected.
selected.pop_back();
}
}
}