小白易懂的回溯算法!!!

res = []    # 定义全局变量保存最终结果
state = []  # 定义状态变量保存当前状态
p,q,r       # 定义条件变量（一般条件变量就是题目直接给的参数）
def back(状态，条件1，条件2，……):
    if # 不满足合法条件（可以说是剪枝）
        return
    elif # 状态满足最终要求
        res.append(state)   # 加入结果
        return 
    # 主要递归过程，一般是带有 循环体 或者 条件体
    for # 满足执行条件
    if  # 满足执行条件
        back(状态，条件1，条件2，……)
back(状态，条件1，条件2，……)
return res

public void backtrack(...){
	if(是一个可行解) 将结果存入集合中;
	if(无备选项或无须进一步搜索) return;
	
	for(所有的备选项){
		if(该备选项不满足约束) continue;
		生成当前节点;
		更新集合;
		子问题backtrack();
		//状态回退
		删除节点;
		回退集合;
	}
}

#include <iostream>
#include <vector>
using namespace std;   
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums)
    {
        vector<vector<int>> ret;
        vector<bool> used(nums.size(), false);
        backTrack(nums, ret,new vector<int>,used);
        return ret;
    }
    void backTrack(vector<int>& nums, vector<vector<int>>& ret, vector<int>* temp, vector<bool>& used)
    {
        //当temp数组存储元素个数等于size时，说明找到了一个解

        if (temp->size() == nums.size())
        {
            ret.push_back(*temp);
        }
        else
        {
           //遍历所有可能子节点
            for (int i = 0; i < nums.size(); i++)
            {
                //如果当前子节点已经被访问过，那么就跳过该子节点，访问下一个子节点
                if (used[i]== true)
                    continue;    
                //设置当前没有访问过的子节点为访问过
                used[i] = true;
                //并加入temp数组
                temp->push_back(nums[i]);
                //temp的数组个数还不等于size，无法构成一个完整的解，因此需要通过递归找到剩余解
                backTrack(nums,ret,temp, used);
                //进行回退操作，将当前子节点的访问性改成未被访问过
                used[i] = false;
                //删除temp数组尾部元素，弹出当前子节点，因为当前子节点不符合规则
                temp->pop_back();
            }
        }

    }
};
void test()
{
    Solution s;
    vector<int> nums = { 1,2,3 };
    vector<vector<int>> ret=s.permute(nums);
    for (int i = 0; i < ret.size(); i++)
    {
        for (int j = 0; j < ret[0].size(); j++)
        {
            cout << ret[i][j] << " ";
        }
        cout << endl;
    }
}
int main() 
{          
    test();
    system("pause");
    return 0;
}

class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
        // 所有数都填完了
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
      vector<vector<int>> ret;
        vector<bool> used(nums.size(), false);
        vector<int> path;
        sort(nums.begin(), nums.end());
        backTrack(nums, ret,path,used);
        return ret;
    }
    void backTrack(vector<int>& nums, vector<vector<int>>& ret, vector<int>& path, vector<bool>& used)
    {
        if (path.size() == nums.size())
        {
            ret.push_back(path);
            return;
        }
        else
        {
            for (int i = 0; i < nums.size(); i++)
            {
                if (used[i] || (i>0&&nums[i] == nums[i-1] && !used[i-1]))
                    continue;
                used[i] = true;
                path.push_back(nums[i]);
                backTrack(nums, ret, path, used);
                used[i] = false;
                path.pop_back();
            }
        }
    }
};

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target)
    {
        vector<vector<int>> ret;
        vector<int> path;
        backTrack(ret, target, path, candidates,0);
        return ret;
    }
    //这里left作用：不能再次选择之前选择过的数字
    void backTrack(vector<vector<int>>& ret, int target, vector<int>& path, vector<int>& cand, int left)
    {
        if (accumulate(path.begin(), path.end(), 0) == target)
        {
            ret.push_back(path);
            return;
        }
        else if (accumulate(path.begin(), path.end(), 0) > target)
        {
            return;
        }
        else
        {
            for (int i = left; i < cand.size(); i++)
            {
                path.push_back(cand[i]);
                backTrack(ret, target, path, cand, i);
                path.pop_back();

            }
        }
    }
};

//迷宫 1为墙 0为通路
int Graph[][6] =
{
		{1, 1, 1, 1, 1, 1},
		{1, 0, 0, 0, 1, 1},
		{1, 0, 1, 0, 0, 1},
		{1, 0, 0, 0, 1 ,1},
		{1, 1, 0, 0, 0, 1},
		{1, 1, 1, 1, 1, 1}
};

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
//迷宫 1为墙 0为通路
int Graph[][6] =
{
		{1, 1, 1, 1, 1, 1},
		{1, 0, 0, 0, 1, 1},
		{1, 0, 1, 0, 0, 1},
		{1, 0, 0, 0, 1 ,1},
		{1, 1, 0, 0, 0, 1},
		{1, 1, 1, 1, 1, 1}
};
//迷宫 起点 终点
void findPath(int(*Graph)[6], int x1, int y1, int x2, int y2)
{
	//存放迷宫路径
	static vector<pair<int,int>> path;
	//找到出口
	if (x1 == x2 && y1 == y2)
	{
		cout << "迷宫路径如下:" << endl;
		path.push_back({ x1,y1 });
		Graph[x1][y1] = -1;
		for_each(path.begin(), path.end(), [](pair<int, int> path) {cout << "{" << path.first << "," << path.second << "}" << endl; });
		return;
	}
	else
	{
		if (Graph[x1][y1]==0)//当前要走的方向为通路
		{
			int di = 0;//方向--右 下 左 上
			int x, y;//记录下一次要走的方向
			for (; di < 4; di++)
			{
				switch (di)
				{
				case 0://右---列加一
				{
					x = x1;
					y = y1 + 1;
					break;
				}
				case 1://下---行加一
				{
					x = x1 + 1;
					y = y1;
					break;
				}
				case 2://左---列减一
				{
					x = x1;
					y = y1 - 1;
					break;
				}
				case 3://上---行减一
				{
					x = x1 - 1;
					y = y1;
					break;
				}
				}
				path.push_back({ x1,y1 });
				Graph[x1][y1] = -1;
			 findPath(Graph, x, y, x2, y2);//更新寻找的起点
			 //回溯加剪枝
			 Graph[x1][y1] = 0;
			 path.pop_back();
			}
		}
	}
}
int main()
{
	findPath(Graph, 1, 1, 4, 4);
	system("pause");
	return 0;
}