递归回溯实战+思想

排列（提供元素无重复，并且不可以重复选择）

排列（提供的元素重复了，但是同个位置的元素不能复选）

组合（提供的元素没有重复，并且可以重复选择相同位置元素）

子集（提供的元素没有重复，且同位置元素只能选择一次）

组合（提供元素不重复，且同位置不能重复选）

排列（提供元素无重复，并且不可以重复选择）

思路：1.根据题意找到base case——>2.然后遍历提供的数据节点，（不可重复选择同一数据节点，并且提供的数据节点都没有重复）——>3.我们利用boolean数据进行判断，当前数据节点是否选择，如果选择过直接continue——>4.没有选择过进行选择逻辑并且修改状态——>5.进入递归函数——>6.回溯，撤销逻辑选择

模板：

/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {// 回溯算法标准框架for (int i = start; i < nums.length; i++) {// 做选择track.addLast(nums[i]);// 注意参数backtrack(nums, i + 1);// 撤销选择track.removeLast();}
}/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {for (int i = 0; i < nums.length; i++) {// 剪枝逻辑if (used[i]) {continue;}// 做选择used[i] = true;track.addLast(nums[i]);backtrack(nums);// 撤销选择track.removeLast();used[i] = false;}
}

例题：

46. 全排列 - 力扣（LeetCode）

 //1.结果集List<List<Integer>>res=new LinkedList<>();public List<List<Integer>> permute(int[] nums) {//1.记录一条路径LinkedList<Integer>track = new LinkedList<>();//2.记录每个元素状态boolean[] used=new boolean[nums.length];backtrack(nums,track,used);return res; }void backtrack(int[]nums,LinkedList<Integer>track,boolean[]used){//1.结束条件if(track.size()==nums.length){res.add(new LinkedList(track));return;}//2.遍历每个元素for(int i=0;i<nums.length;i++){//2.1排除不合法的选择if(used[i]){continue;}//2.2对当前元素做选择track.add(nums[i]);used[i]=true;backtrack(nums,track,used);//2.3进行回溯track.removeLast();used[i]=false;}}

排列（提供的元素重复了，但是同个位置的元素不能复选）

不同之处：和上述思路差不多，加了一个剪枝操作，因为提供的元素有重复（比如：【1，2，2】），所以我们需要固定重复元素的位置，防止出现重复结果

打个比方，就以 nums = [1,2,2] 为例，为了区别两个 2 是不同元素，后面我们写作 nums = [1,2,2']

——>显然，两条值相同的相邻树枝会产生重复

剪枝：需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]&&used[i-1] (排列情况)

比如输入 nums = [1,2,2',2'']，2' 只有在 2 已经被使用的情况下才会被选择，同理，2'' 只有在 2' 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定

if (i > 0 && nums[i] == nums[i - 1] && used[i-1]) continue;

模板：

Arrays.sort(nums);
/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {// 回溯算法标准框架for (int i = start; i < nums.length; i++) {// 剪枝逻辑，跳过值相同的相邻树枝if (i > start && nums[i] == nums[i - 1]) {continue;}// 做选择track.addLast(nums[i]);// 注意参数backtrack(nums, i + 1);// 撤销选择track.removeLast();}
}Arrays.sort(nums);
/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {for (int i = 0; i < nums.length; i++) {// 剪枝逻辑if (used[i]) {continue;}// 剪枝逻辑，固定相同的元素在排列中的相对位置if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {continue;}// 做选择used[i] = true;track.addLast(nums[i]);backtrack(nums);// 撤销选择track.removeLast();used[i] = false;}
}

例题：

47. 全排列 II - 力扣（LeetCode）

class Solution {List<List<Integer>> perResult = new LinkedList<>();LinkedList<Integer> perTrack = new LinkedList<>();boolean[] used;public List<List<Integer>> permuteUnique(int[] nums) {//1.先排序Arrays.sort(nums);used = new boolean[nums.length];//2.递归函数permuteUniqueHelper(nums);return perResult;}void permuteUniqueHelper(int[] nums) {//1.base:子路径的结束条件if (perTrack.size() == nums.length) {perResult.add(new LinkedList<>(perTrack));return;}//2.遍历nums所有数据for (int i = 0; i < nums.length; i++) {//2.1判断当前节点有没有使用过——>使用过就不能再次出现if (used[i]) continue;//2.2剪枝逻辑，固定排序位置if (i > 0 && nums[i] == nums[i - 1] && used[i-1]) continue;//2.3添加当前节点进子序列perTrack.add(nums[i]);used[i]=true;permuteUniqueHelper(nums);//2.4回溯perTrack.removeLast();used[i]=false;}}}

组合（提供的元素没有重复，并且可以重复选择相同位置元素）

一般作用于求和类组合题目上，像这种提供元素不重复（重复元素，要考虑去重->剪枝即可），可以重新选择（删除去重逻辑->start不+1）

39. 组合总和 - 力扣（LeetCode）

class Solution {List<List<Integer>> res = new LinkedList<>();
// 记录回溯的路径
LinkedList<Integer> track = new LinkedList<>();
// 记录 track 中的路径和
int trackSum = 0;public List<List<Integer>> combinationSum(int[] candidates, int target) {if (candidates.length == 0) {return res;}backtrack(candidates, 0, target);return res;
}// 回溯算法主函数
void backtrack(int[] nums, int start, int target) {// base case，找到目标和，记录结果if (trackSum == target) {res.add(new LinkedList<>(track));return;}// base case，超过目标和，停止向下遍历if (trackSum > target) {return;}// 回溯算法标准框架for (int i = start; i < nums.length; i++) {// 选择 nums[i]trackSum += nums[i];track.add(nums[i]);// 递归遍历下一层回溯树// 同一元素可重复使用，注意参数backtrack(nums, i, target);// 撤销选择 nums[i]trackSum -= nums[i];track.removeLast();}
}}

子集（提供的元素没有重复，且同位置元素只能选择一次）

思路：只能选择一次，每次进入递归的时候，利用一个变量+1（start+1）防止重复踩到相同位置元素——>1.因为是组合类题目，允许空集，所以前序位置直接结果集加一个子序列——>2.每次添加一个元素进入递归函数后——>结果集都会重新加一个子序列（也是通过start控制相同位置不重复访问的，利用track子序列添加元素，然后递归后慢慢撤销回溯，但是像我们以下的图，到i=2他就进不了1这个位置了）

模板：

List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> track = new LinkedList<>();// 主函数
public List<List<Integer>> subsets(int[] nums) {backtrack(nums, 0);return res;
}// 回溯算法核心函数，遍历子集问题的回溯树
void backtrack(int[] nums, int start) {// 前序位置，每个节点的值都是一个子集res.add(new LinkedList<>(track));// 回溯算法标准框架for (int i = start; i < nums.length; i++) {// 做选择track.addLast(nums[i]);// 通过 start 参数控制树枝的遍历，避免产生重复的子集backtrack(nums, i + 1);// 撤销选择track.removeLast();}
}

例题：

78. 子集 - 力扣（LeetCode）

class Solution {//1.结果集List<List<Integer>> result=new LinkedList<>();public List<List<Integer>> subsets(int[] nums) {//2.单节点路径LinkedList<Integer> track=new LinkedList<>();//3.递归函数back(nums,0,track);return result;}void back(int[]nums,int start,LinkedList<Integer>track){//1.首先添加一个空集合,对于后面就是添加有数据的节点result.add(new LinkedList<>(track));//2.回溯得到组合框架for(int i=start;i<nums.length;i++){//2.1添加节点track.addLast(nums[i]);//2.2进行递归back(nums,i+1,track);//2.3回溯track.removeLast();}}
}

组合（提供元素不重复，且同位置不能重复选）

思路：跟子集一样，

你比如说，让你在 nums = [1,2,3] 中拿 2 个元素形成所有的组合，你怎么做？

稍微想想就会发现，大小为 2 的所有组合，不就是所有大小为 2 的子集嘛。

所以我说组合和子集是一样的：大小为 k 的组合就是大小为 k 的子集。

77. 组合 - 力扣（LeetCode）

class Solution {/*** 3.组合问题，找出给定数组中指定个数的组合** @param n：指定范围1-n* @param k：指定个数k个* @return*/List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> track = new LinkedList<>();// 主函数
public List<List<Integer>> combine(int n, int k) {backtrack(1, n, k);return res;
}void backtrack(int start, int n, int k) {// base caseif (k == track.size()) {// 遍历到了第 k 层，收集当前节点的值res.add(new LinkedList<>(track));return;}// 回溯算法标准框架for (int i = start; i <= n; i++) {// 选择track.addLast(i);// 通过 start 参数控制树枝的遍历，避免产生重复的子集backtrack(i + 1, n, k);// 撤销选择track.removeLast();}
}}