每日OJ题_DFS回溯剪枝①_力扣46. 全排列（回溯算法简介）

目录

回溯算法简介

力扣46. 全排列

解析代码

---

回溯算法简介

回溯算法是一种经典的递归算法，通常⽤于解决组合问题、排列问题和搜索问题等。

        回溯算法的基本思想：从一个初始状态开始，按照⼀定的规则向前搜索，当搜索到某个状态无法前进时，回退到前一个状态，再按照其他的规则搜索。回溯算法在搜索过程中维护一个状态树，通过遍历状态树来实现对所有可能解的搜索。

        回溯算法的核心思想：“试错”，即在搜索过程中不断地做出选择，如果选择正确，则继续向前搜索，否则，回退到上一个状态，重新做出选择。回溯算法通常用于解决具有多个解，且每个解都需要搜索才能找到的问题。

        回溯算法的模板：

void backtrack(vector<int>& path, vector<int>& choice, ...)
{
	// 满⾜结束条件
	if (/* 满⾜结束条件 */)
	{
		// 将路径添加到结果集中
		res.push_back(path);
		return;
	}
	// 遍历所有选择
	for (int i = 0; i < choices.size(); i++)
	{
		// 做出选择
		path.push_back(choices[i]);
		// 做出当前选择后继续搜索
		backtrack(path, choices);
		// 撤销选择
		path.pop_back();
	}
}

        其中， path表示当前已经做出的选择， choices表示当前可以做的选择。在回溯算法中，我们需要做出选择，然后递归地调用回溯函数。如果满足结束条件，则将当前路径添加到结果集中。

        否则，我们需要撤销选择，回到上一个状态，然后继续搜索其他的选择。回溯算法的时间复杂度通常较高，因为它需要遍历所有可能的解。但是，回溯算法的空间复杂度较低，因为它只需要维护一个状态树。在实际应用中，回溯算法通常需要通过剪枝等方法进行优化，以减少搜索的次数，从而提高算法的效率。

        回溯算法是一种非常重要的算法，可以解决许多组合问题、排列问题和搜索问题等。回溯算法的核心思想是搜索状态树，通过遍历状态树来实现对所有可能解的搜索。回溯算法的模板非常简单，但是实现起来需要注意一些细节，比如何做出选择、如何撤销选择等。

---

力扣46. 全排列

46. 全排列

难度 中等

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

class Solution {
public:
    vectorint>> permute(vector<int>& nums) {
 
};

---

解析代码

之前练习next_permutation时写过，代码在下面注释起来了。

 

深搜的思路是循环模仿遍历树的结点，到叶子结点就返回，不是就进入循环。

        在下面for循环里要考虑这个位置要填哪个数。根据题目要求我们肯定不能填已经填过的数，因此很容易想到的一个处理手段就是定义一个标记数组来标记已经填过的数，那么在填这个数的时候我们遍历题目给定的所有数，如果这个数没有被标记过，我们就尝试填入，并将其标记，继续尝试填下一个位置，

        回溯的时候要撤销这一个位置填的数以及标记，并继续尝试其他没被标记过的数。

class Solution {
    vectorint>> ret;
    vector<int> path;
    bool cheak[6] = {0}; // 映射下标->数字是否用过->剪枝
    
public:
    vectorint>> permute(vector<int>& nums) {
        dfs(nums);
        return ret;
    }
 
    void dfs(vector<int> nums)
    {
        if(nums.size() == path.size())
        {
            ret.push_back(path);
            return;
        }
        for(int i = 0; i < nums.size(); ++i)
        {
            if(cheak[i] == false) // 如果没有用过才使用->剪枝
            {
                path.push_back(nums[i]);
                cheak[i] = true;
                dfs(nums); // 此时路径已经加上一个了，在让其进入递归
 
                path.pop_back(); // 回溯，恢复现场，（递归往回走了）
                cheak[i] = false;
            }
        }
    }
};
 
// class Solution {
// public:
//     vector> permute(vector& nums) {
//         vector> vv;
//         sort(nums.begin(), nums.end());
//         do
//         {
//             vv.push_back(nums);
//         }while(next_permutation(nums.begin(), nums.end()));
//         return vv;
//     }
// };