数据结构与算法：回溯法之全排列

题源:
46.全排列
初次接触回溯法真的好难&＃xff0c;debug了半天才了解到了其中的具体原理过程&＃xff0c;接下来我引用weiwei哥的讲解和我自己的一些理解&＃xff0c;希望可以为读者讲明白其中的原理。
什么是回溯法&＃xff1f;
简单来说&＃xff0c;就是分步地去解决问题&＃xff0c;当发现某一步不符合我们的条件时就跳回到上一个步骤&＃xff0c;再次尝试其它的路径寻求当前问题的解决方案。类似于dfs(深度优先搜索)
回溯法的具体步骤
1.choose:选择当前"迷宫"的一条路径
2.explore:判断当前路径是否满足条件
3.un-choose:如果成功就做个已经访问过的标记&＃xff0c;反之则退回到上一步
本质是递归&＃43;某些限制条件(暴力搜索&＃43;剪枝)
如何实现
遍历所给数组&＃xff0c;采用空间换时间的方法定义一个visited数组表示当前数是否被遍历&＃xff0c;false时加入curList中&＃xff0c;递归调用dfs方法。un-choose阶段中再回溯&＃xff0c;把当前值去掉
代码具体实现

package com.algorithm.recall;import java.util.ArrayList;
import java.util.List;/*** &＃64;program: Java IDEA Projects* &＃64;create: 2022-01-24 20:40**/
public class permute {public List<List<Integer>> permute(int[] nums) {//定义一个动态数组结果集List<List<Integer>> res&＃61;new ArrayList<>();//进行一个简单的判断if(nums.length<1) return res;//定义存储当前结果集合的listList<Integer> curList&＃61;new ArrayList<>();//定义visited数组标记当前数是否被访问boolean[] visited&＃61;new boolean[nums.length];//递归调用dfsdfs(nums,curList,visited,res);return res;}/**** &＃64;Param: [nums:输入数组,* path:存储当前结果的数组,* visited:当前数是否已经被访问,* res:结果集]* &＃64;return: void* &＃64;Date: 2022/1/25*/private void dfs(int[] nums, List<Integer> curList, boolean[] visited,List<List<Integer>> res) {//满足条件时加入结果集if(curList.size() &＃61;&＃61; nums.length) {res.add(new ArrayList<>(curList));return;}for(int i&＃61;0;i<nums.length;i&＃43;&＃43;) {//如果当前数已经被标记访问过,那么就跳过if(visited[i]) continue;//未被标记就加入当前结果集,并标记这个数已被访问curList.add(nums[i]);visited[i]&＃61;true;//递归调用dfs(nums, curList, visited, res);//满足条件时回溯,即un-choose阶段//将最后一个数返回相当于回到上一个步骤//将上一个步骤的数设为false,选择其它的路径curList.remove(curList.size()-1);visited[i]&＃61;false;}}}

dubug具体实现过程,以nums&＃61;[1,2,3]为例
i&＃61;0时,即numso[i]&＃61;1;

i&＃61;1时,即nums[i]&＃61;2;

i&＃61;2时满足条件加入到结果集中

递归返回到上一个循环中执行dfs下面的语句&＃xff0c;即将3这个数从当前结果集中移除&＃xff0c;并将3对应的下标i&＃61;2设为false。注意此时的i是在循环里的&＃xff0c;执行完之后i不满足循环的条件跳出了循环。此时再次返回递归的上一个条件…以此循环