核心思想：回溯算法

回溯类似于穷举，会调用递归。当遇到要穷举一些结果的题目的时候，可以使用回溯，回溯比穷举好的地方在于，它可以做剪枝。是深度优先搜索（dfs）的一种

void dfs() {
  if(边界条件){
     保存结果;
     return;
  }
  for (int i = 0 ; i<n ; i++){
     if (剪枝条件) {
        continue;
     }
     修改全局变量;
      if (子状态满足条件) {
        dfs (子状态)
     }
     恢复全局变量;
  }
}

输入一个不含重复元素的数组，返回这个数组中元素的所有全排列结果

图片 1.png

vector<vector<int>> permute (vector<int>& nums) {
    vector<vector<int>> res;
    visited = vector<bool>(nums.size(), false);
    vector<int> p;
    dfs(nums, 0, p);
    return res;
}

void dfs (vector<int>& nums, int index,  vector<int>& p) {
     if (index == nums.size()) {
        res.push_back(p); // 保存结果
        return;
    }
    for (int i = 0; i < nums.size() ; i++) {
      // 不重复
      if (visited[i] == true) continue;
      // 修改全局变量
      visited[i] =  true;
      p.push_back(nums[i]);
      // 子状态
      dfs (nums, index+1, p); 
      // 恢复全局变量
      visited[i] =  false;
      q.pop_back();
    }
    return;
}

数组中有重复元素，输出全排列

vector<vector<int>> permute (vector<int>& nums) {
    vector<vector<int>> res;
    visited = vector<bool>(nums.size(), false);
    vector<int> p;
    sort(nums.begin(), nums.end());// 排序
    dfs(nums, 0, p);
    return res;
}

void dfs (vector<int>& nums, int index,  vector<int>& p) {
     if (index == nums.size()) {
        res.push_back(p); // 保存结果
        return;
    }
    for (int i = 0; i < nums.size() ; i++) {
      // 不重复
      if (i>0 && nums[i-1] == nums[i] && visited[i-1] == false) continue;//同层去重
      if (visited[i] == true) continue;
      // 修改全局变量
      visited[i] =  true;
      p.push_back(nums[i]);
      // 子状态
      dfs (nums, index+1, p); 
      // 恢复全局变量
      visited[i] =  false;
      q.pop_back();
    }
    return;
}