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

  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();
         }
     }
 }

Ref.