**
返回该数组存在的所有访问顺序
大致执行流程:
首先选取一个元素作为起点,保存该元素;再访问下一个元素并保存,重复上述流程,直到访问所有元素;将该路径添加到res中
回溯到上一步,更换访问顺序,直到访问完所有元素;重复上述流程,直到上一步可选元素全部访问完;将该路径添加到res中
回溯到上上步,更换访问顺序,直到访问完所有元素;重复上述流程,直到上一步可选元素全部访问完;将该路径添加到res中
.......
直到回溯到第一步,并访问完所有可选元素,此时得出所有访问顺序
所需参数:
List<Integer> tempResult 临时保存单次结果
int[] used 用于判断可访问元素;访问过对应位置设为1 未访问为0
操作细化:
终止条件:
tempResult长度与nums长度相同;代表访问完所有元素,保存到res中并终止
访问方式(for循环 + 递归):
利用used判断当前元素是否被访问
未访问过则添加到tempResult中,并修改used;访问过则不做处理,迭代元素再次尝试
递归调用添加下一个元素;遇到访问过的元素不做处理,通过for循环迭代元素,可访问才进行处理
回溯:
回退used与tempResult的状态
*/
class Solution {//保存所有结果private List<List<Integer>> res = new ArrayList<>();//临时保存单次结果private List<Integer> tempResult = new ArrayList<>();//用于判断可访问元素(元素是否被访问)private int[] used; //访问过对应位置设为1 未访问为0//避免重复传参private int[] nums;public List<List<Integer>> permute(int[] nums) {/**返回该数组存在的所有访问顺序大致执行流程:首先选取一个元素作为起点,保存该元素;再访问下一个元素并保存,重复上述流程,直到访问所有元素;将该路径添加到res中回溯到上一步,更换访问顺序,直到访问完所有元素;重复上述流程,直到上一步可选元素全部访问完;将该路径添加到res中回溯到上上步,更换访问顺序,直到访问完所有元素;重复上述流程,直到上一步可选元素全部访问完;将该路径添加到res中.......直到回溯到第一步,并访问完所有可选元素,此时得出所有访问顺序所需参数:List<Integer> tempResult 临时保存单次结果int[] used 用于判断可访问元素;访问过对应位置设为1 未访问为0操作细化:终止条件:tempResult长度与nums长度相同;代表访问完所有元素,保存到res中并终止访问方式(for循环 + 递归):利用used判断当前元素是否被访问未访问过则添加到tempResult中,并修改used;访问过则不做处理,迭代元素再次尝试递归调用添加下一个元素;遇到访问过的元素不做处理,通过for循环迭代元素,可访问才进行处理回溯:回退used与tempResult的状态*/this.nums = nums;this.used = new int[nums.length];backtrack();return res;}private void backtrack() {//代表所有元素都被访问 保存本次结果并returnif(tempResult.size() == nums.length) {//res.add(tempResult); 浅拷贝,会因后续的回溯导致已保存的结果改变//深拷贝res.add(List.copyOf(tempResult));return;}for(int i = 0; i < nums.length; i++) {//未被访问过才可添加到tempResult中if(used[i] == 0) {tempResult.add(nums[i]);used[i] = 1; //修改访问状态backtrack(); //递归调用,添加下一个元素//回溯 回退used与tempResult的状态used[i] = 0;tempResult.remove(tempResult.size() - 1); //从末尾元素开始删除}}}
}
)
