回溯算法总结_回溯算法时间复杂度

常用回溯算法题目是排列问题、组合问题、皇后问题

首先给出多叉树遍历框架和回溯算法的核心框架，回溯算法的知识点总结如下：

1、回溯算法本身是一种暴力穷举算法

2、穷举的过程就是遍历一个多叉树的过程

3、回溯算法的代码框架和多叉树遍历的代码框架相似

• 排列问题

(1)题目链接：Leetcode46 全排列问题

本题可以通过交换数组元素的位置来做，这个部分在蓝桥杯总结过程中已经用过了。另一种是通过遍历树来来解决，本题的一个遍历树是这样的

ref[1]:图源

代码是这样的

std::vector<std::vector<int> > ans;
void backtracing(std::vector<int>& nums, std::vector<int> &path){
     if(path.size()==nums.size()){ans.push_back(path);}
     for(int i = 0; i < nums.size(); i++){
         if(std::find(path.begin(), path.end(), nums[i])!=path.end()){continue;}
         path.push_back(nums[i]);
         backtracing(nums, path);
         path.pop_back();
     }
}
vector<vector<int>> permute(vector<int>& nums) {
     std::vector<int> path;
     backtracing(nums, path);
     return ans;
}

时间复杂度分析：回溯算法由于其遍历的特点，复杂福一般都比较高，有些问题分析起来也很复杂。一些回溯算法解决的问题，剪枝剪得好的话，复杂度会降低一点，因此分析最坏时间复杂度的意义也不是很大。但是还是是情况而定。

递归函数的复杂度=递归函数本身的复杂度*递归函数被调用的次数。所以这里的回溯算法的时间复杂度为O(N*N*N!)(find函数查找也需要O(N)的复杂度)，空间复杂度也是O(N*N!)

2、变种

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

这种情况就需要剪枝了，具体而言需要对递归树进行剪枝

这个剪枝的过程的判断是这样的

if(visited[i]){continue;}
 
if(i>0&&nums[i]==nums[i-1]&&visited[i-1]==false){continue;}

 代码是这样的

    std::vector<std::vector<int>> ans;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        std::vector<bool> visited(nums.size(),false);
        std::vector<int> path;
        backtracing(nums, path, visited);
        return ans;
    }
    void backtracing(std::vector<int>& nums, std::vector<int> &path, std::vector<bool>& visited){
        if(path.size()>=nums.size()){
            ans.push_back(path);
            return;
        }
    
        for(int i = 0; i < nums.size(); i++){
            if(visited[i]){continue;}
            if(i>0&&nums[i]==nums[i-1]&&visited[i-1]==false){continue;}
            
            path.push_back(nums[i]);
            visited[i] = true;
            backtracing(nums, path,visited);
            visited[i] = false;
            path.pop_back();
            
        }
    }

ref[1]:Leetcode46 全排列

ref[2]:Leetcode46 题解

ref[3]:leetcode47 全排列II

ref[4]:leetcode47 题解

ref[5]: 【labuladong】回溯算法核心套路详解