1 模板

1.1 思路

  说到深度搜索与广度搜索，我们一般会先想到图。而一些题目是没有明显的图，需要我们做一些抽象。

  对于一个图的深度优先搜索，我们一般需要三个

  （1）path：用于保存已经搜索过和节点及顺序。

  （2）closet：未被搜索的节点集合。
  （3）edges：边集合，用于描述closet中元素的关系。

  如果我们假设closet和path都是数组结构，我们还需要一个used的数组来标志closet中哪个元素已经使用过，则一个深度优先搜索的伪代码：

  dfs(closet, used, path, level) {
    if(level == closet.size()){
      // 遍历完一条路径
      return;
    }
    for(int i = 0; i < closet.size(); i++){
      // 如果当前节点已经在path中，或者path里保存的最后一个节点到当前节点不存在边
      if(used[i] || (path[level], closet[i]) not in edges) continue;
      path[level] = closet[i];
      used[i] = 1;
      dfs(closet, used, path, level+1);
      used[i] = 0;
    }
  } 

1.2 时间复杂度

  每层递归都要遍历一遍used数组长度为n，我们假设closet里有[1，2，3]，这3个元素，则搜索这个集合的过程如下图所示。

复杂度示例

  可以看到，第一层的点派生出了3个子节点，第二层每个节点只派生2个子节点，而第三层每个节点只能派生1个子节点。因此，整棵树的节点数为 n!。
  由上可知，算法时间复杂度为 n*n!

2 具体样例

2.1 求数据的全排列，无重复数据

2.1.1 套用模板的解法

  了解了DFS的模板之后，我们首先需要抽象出三个对象：
（1）path：一种排列。
（2）closet：数据集合。
（3）edges：某一个元素后台能接哪个元素，容易知道，全排列中，每个元素后台都可以接任意元素。
  由此，我们根据模板写出：求全排列的代码。

  vector<vector<int>> result;
  void dfs(vector<int>& nums, vector<bool>& used, vector<int>& path, int level){
    if(level >= nums.size()) {
      result.push_back(path);
      return;
    }
    for(int i = 0; i< nums.size(); i++) {
      if(used[i]) continue;
      path[level] = nums[i];
      used[i] = true;
      dfs(nums, used, path, level+1);
      used[i] = false;
  }

2.1.2 基于模板的优化

   聪明的孩子会发现，在这个题目中，其实我们不需要用used来记录当前搜索节点closet中元素的使用情况，我们可以把已经使用的元素移动closet数组的前半部分，而没使用的放在后半部分。具体实现如下：

  vector<vector<int>> result;
  void dfs(vector<int>& nums, int unusedIdx, vector<int>& path, int level){
    if(level >= nums.size()) {
      result.push_back(path);
      return;
    }
    for(int i = unusedIdx; i< nums.size(); i++) {
      path[level] = nums[i];
      swap(nums[unusedIdx], nums[i]);
      dfs(nums, unusedIdx+1, path, level+1);
      swap(nums[unusedIdx], nums[i]);
  }