# |Algo| Backtracking

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.
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:

1. N-Queens
2. N-Queens II
3. Combination Sum
4. Combination Sum II
5. Combination Sum III
6. Permutations
7. Permutations II
8. Subsets
9. Subsets II
10. 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();
}
}
}``````