backtracking in a glance

首先系统地介绍一下backtracking这个方法本质是建立在递归的基础上，不断尝试新的路径，这里关键是每次尝试完以后需要退回来也就是回溯。这里开篇讲述了一个希腊神话，传说迷宫里面有个怪兽Minotaur会吃人，有个年轻人Theseus自告奋勇进入迷宫去杀死了Minotaur，但是怎么出来呢？这里其实就需要backtracking,即尝试所有可能可以走的路径直到可以走出一个通路，从这里我们也可以看出backtracking不是一个有效的解法有点类似于穷举法。整体来看，backtracking算法一般可以用以下的描述来表示：

如果你已经找到了解决方案，那么返回成功
for(现在位置可以的所有可能选择）｛
  选择其中一个方案然后沿着路径前进一步
  使用递归的方法从新的位置解决问题
  如果新的位置可以成功解决，向上一级返回成功
  从现在位置恢复到循环之前的位置
 ｝
 如果到这里表示仍然没有成功，返回失败

从这里我们可以看的出，这个算法的复杂度是指数级的，因此从复杂度这个角度看backtracking不是一个有效的解法。

数组

下面我们来看一下backtracking在数组里面的几个例子
例题：subset
复杂度： 时间复杂度O(2^n)，空间复杂度O(n)
分析：根据题意这里有几个地方值得注意，首先输出的subset必须是递减的，因此我们必须首先把原数组进行排序,对于每一个元素可以选择加入或者不加入，一共有n个这样的元素因此for循环是整个原来的vector的长度，而这里会遗忘一个空subset在recursive call之前要把它加上。

class Solution {
 public:
     vector<vector<int> > subsets(vector<int> &S) {
        sort(S.begin(), S.end());
        vector<vector<int> > result;
        vector<int> path;
        result.push_back(vector<int>(0));
        helper(S, path, 0, result);
        return result;
    }
   private:
       static void helper(const vector<int> &S, vector<int> &path, int step,
           vector<vector<int> > &result) {
             for(int i = step; i < S.size(); ++i){
              path.push_back(S[i]);
              result.push_back(path);
              helper(S, path, i+1, result);
              path.pop_back();
            }            
        }
    };

例题： subset II
复杂度： 时间复杂度O(2^n),空间复杂度O(n)
分析：这里需要判断一个重复元素的问题，也就是是否存在当前元素与前一个元素相等如果相等就skip掉，以免造成重复（因为这里元素已经排序过，重复元素之可能出现在邻近位置）。 这道题本质上和上一题类似，上一题没有重复数，因此一个元素可以选择0次或者1次。这道题有重复数也就是说一个元素可以出现0次或者若干次。

class Solution {
   public:
   vector<vector<int> > subsetsWithDup(vector<int> &S) {
      sort(S.begin(), S.end());
      vector<vector<int> > result;
      vector<int> path;
      helper(S, S.begin(), path, result);
      return result;
     }  
  private:
   void helper(vector<int> &S, vector<int>::iterator start, 
   vector<int> &path, vector<vector<int> > &result){
       result.push_back(path);
      
     for(auto i = start; i < S.end(); i++){
          if(i != start && *i == *(i-1)) continue;
           path.push_back(*i);
           helper(S, i+1, path, result);
           path.pop_back();
        }
   }
 };

例题： Combination Sum
复杂度： 时间复杂度O(2^n), 空间复杂度 O(2^n) ?
分析：这道题比之前subset系列题多了一个限制条件，需要找到所有的combination之和满足某一个特定的值target,因此在之前的框架基础上需要加一些剪枝的判断，这道题就是目前组合之和是否等于或者小于target, 如果等于就把当前的组合放入到结果中，如果小于target,可以继续在剩余的数中选取合适的值去满足target，但是如果是大于就立刻停止循环下去这样可以减少不必要的时间浪费。

  class Solution {
     public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
             sort(candidates.begin(), candidates.end());
             vector<vector<int> > result;
             vector<int> path;
             helper(path, candidates.begin(), candidates, result, target, 0);
             return result;
        }
      private:
       void helper(vector<int> &path, vector<int>::iterator start, 
          const vector<int>  &candidates,  vector<vector<int> > &result, 
                     int target, int current){
              if(accumulate(path.begin(), path.end(), 0) == target){ 
                    result.push_back(path);                    
                    return;
                  }

              for(auto i = start; i < candidates.end(); ++i){
                    if(current + *i > target)
                        break;
                
                    path.push_back(*i);
                    helper(path, i, candidates, result, target, current + *i);
                    path.pop_back();                   
           }
       }
    };

例题： Combination Sum II
复杂度：时间复杂度O(2^n), 空间复杂度O(2^n)?
分析： 思路跟subset II差不多，判断一下是否与前一个数重复，其他与前一题一样。

 class Solution {
  public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
       sort(num.begin(), num.end());
       vector<int> path;
       vector<vector<int> > result;
       helper(path, result, target, num, num.begin(), 0);
       return result;
    }
 private:
    void helper(vector<int> &path, vector<vector<int> > &result, 
    int target, vector<int> &num, vector<int>::iterator start, int current){
       if(current == target){
           result.push_back(path);
           return;
        }
    
        int previous = -1;
        for(auto i = start; i < num.end(); ++i){
             if(previous == *i) continue;
             if(current + *i > target) break;
        
             previous = *i;
             path.push_back(*i);
             helper(path, result, target, num, i+1, current + *i);
             path.pop_back();            
         } 
      }
   };

例题： Combinations
复杂度：时间复杂度O(n!),空间复杂度O(n)
分析： 这道题比之前几道题更简单，不需要对任何数组排序。

class Solution {
public:
   vector<vector<int> > combine(int n, int k) {
      vector<int> path;
      vector<vector<int> > result;
      helper(path, result, n, k, 1);
      return result;
  }
private:
    void helper(vector<int> &path, 
    vector<vector<int> > &result, int n, int k, int start){
       if(path.size() == k)
          result.push_back(path);
   
      for(int i = start; i <= n; ++i ){
         path.push_back(i);
         helper(path, result, n, k, i+1);
         path.pop_back();
      }  
  }
};

例题：Permutations
复杂度：时间复杂度O(n!),空间复杂度O(n).
分析：与之前的不同，这里循环的次数是固定的必须从头开始，这里条件中原来的数组没有重复数，因此需要判断加入进去的数是否已经出现过了。

   class Solution {
      public:
           vector<vector<int> > permute(vector<int> &num) {
                sort(num.begin(), num.end());
                vector<vector<int> > result;
                vector<int> path;
                helper(result, path, num);
                return result;
               }
       private:
              void helper(vector<vector<int> > &result, vector<int> &path, 
                      const vector<int> &num){
                 if(path.size() == num.size()){
                     result.push_back(path);
                     return;
                }
             
               for(auto i : num){
                    auto pos = find(path.begin(), path.end(), i);
                    
                    if(pos == path.end()){
                        path.push_back(i);
                        helper(result, path, num);
                        path.pop_back();
                      }
                  }
                }
            };

例题： Permutations II
复杂度： 时间复杂度O(n!), 空间复杂度O(n)
分析：有了重复数，问题变得更加复杂，除了判断与之前的一个数是否相同以外还需要看前一个数是否已经使用了，因此需要多一个数组来储存信息。

 class Solution {
   public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
    sort(num.begin(), num.end());
    vector<int> path;
    vector<int> visited(num.size(), 0);
    vector<vector<int> > result;
    helper(path, result, num, visited);
    return result;
}
private:
   void helper(vector<int> &path, vector<vector<int> > &result, vector<int> &num, vector<int> &visited){
   if(num.size() == path.size())
      result.push_back(path);
    
   for(int i = 0; i < num.size(); ++i){
       if(visited[i] == 0){
           if(i > 0 && num[i] == num[i-1] && visited[i-1] == 1)
             continue;
             
           visited[i] = 1;
           path.push_back(num[i]);
           helper(path, result, num, visited);
           path.pop_back();
           visited[i] = 0;
       }
   }
 }
};

字符串

例题：Letter Combinations of A Phone Number
复杂度:时间复杂度O(3^n), 空间复杂度O(n).
分析：这里有两个地方需要注意，可以用一个private vector去存储每一个数字对应的letter,这样可以在任何一个函数里面调用它，并且使用vector可以巧妙的使用数组的index来map而不是用其他hashtable. 第二个地方就是base case的细节问题，当把path push back进结果以后，该函数就必须返回不再执行之后的操作。

class Solution {
public: 
    vector<string> letterCombinations(string digits) {
         vector<string> result;
         helper(result, digits, "", 0);
         return result;
       }
private:
     const vector<string> mapped {" ", "", "abc", "def",
        "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

     void helper(vector<string> &result, string digits, string path, int step){
         if(step == digits.size()){
             result.push_back(path);
             return;
           }
    
          for(auto c : mapped[digits[step] - '0']){
              path.push_back(c);
              helper(result, digits, path, step + 1);
              path.pop_back();
         }
     } 
  };