一、概述
解决一个回溯问题，实际上就是一个决策树的遍历过程。只需要考虑以下三个问题：
（1）路径：已经做出的选择。
（2）选择列表：也就是你当前所做出的选择。
（3）结束条件：也就是到达决策树底层，无法在做出的条件。
二、代码模板
result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择
核心：其实就是for循环里面的递归，在递归调用之前做选择，在递归调用之后撤销选择。
三、代码实战
（1）无重复的全排列：非交换
class Solution{ List<List<Integer>> res=new ArrayList<>(); public List<List<Integer>>premute(int []nums){ List<Integer>track=new ArrayList<>(); backTrack(res,list); return res; } // 路径：记录在 track 中 // 选择列表：nums 中不存在于 track 的那些元素 // 结束条件：nums 中的元素全都在 track 中出现 public void backTrack(int nums[],List<Integer>track){ //触发结束条件 if(nums.length==track.size()){ res.add(new ArrayList<>(track)); return; } for(int i=0;i<nums.length;i++){ if(track.contains(nums[i])){ continue; } track.add(nums[i]); backTrack(res,track); track.remove(track.size()-1); } } }
（2）无重复排列：非交换
class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); int[] visited = new int[nums.length]; backtrack(res, nums, new ArrayList<Integer>(), visited); return res; } private void backtrack(List<List<Integer>> res, int[] nums, ArrayList<Integer> tmp, int[] visited) { if (tmp.size() == nums.length) { res.add(new ArrayList<>(tmp)); return; } for (int i = 0; i < nums.length; i++) { if (visited[i] == 1) continue; visited[i] = 1; tmp.add(nums[i]); backtrack(res, nums, tmp, visited); visited[i] = 0; tmp.remove(tmp.size() - 1); } } }
（3）无重复的全排列：交换
class Solution { List<Integer>res=new ArrayList<>(); public List<List<Integer>>premute(int[] nums){ List<Integer>track=new ArrayList<>(); backTrack(nums,track,0); return res; } public void backTrack(int[] nums,List<Integer>track,int cur){ if(cur==nums.length){ track=new ArrayList<>(); for(int item:nums){ track.add(item); } } for(int i=cur;i<nums.length;i++){ swap(nums,i,cur); backTrack(nums,track,cur); swap(nums,i,cur); } } public void swap(int nums[],int i,int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }
原文：https://www.cnblogs.com/hdc520/p/12548568.html