系列文章目录
算法及数据结构系列 - 二分查找
算法及数据结构系列 - BFS算法
算法及数据结构系列 - 动态规划
算法及数据结构系列 - 双指针

回溯算法

框架思路

思路

解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：

1. 路径：也就是已经做出的选择。
2. 选择列表：也就是你当前可以做的选择。
3. 结束条件：也就是到达决策树底层，无法再做选择的条件。

代码框架

result = []
def backtrack(路径, 选择列表):if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:做选择backtrack(路径, 选择列表)撤销选择

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」

经典题型

全排列问题

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

List<List<Integer>> res = new LinkedList<>();/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {// 记录「路径」LinkedList<Integer> track = new LinkedList<>();backtrack(nums, track);return res;
}// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track) {// 触发结束条件if (track.size() == nums.length) {res.add(new LinkedList(track));return;}for (int i = 0; i < nums.length; i++) {// 排除不合法的选择if (track.contains(nums[i]))continue;// 做选择track.add(nums[i]);// 进入下一层决策树backtrack(nums, track);// 取消选择track.removeLast();}
}

子集问题

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();public List<List<Integer>> subsets(int[] nums) {helper(new LinkedList<Integer>(), nums, 0);return res;}public void helper(LinkedList<Integer> path, int[] nums, int fromIndex){res.add(new LinkedList<Integer>(path));for(int i = fromIndex; i < nums.length; i++){path.add(nums[i]);helper(path, nums, i + 1); // 每次只能选择选过元素之后的元素path.removeLast();}}
}

组合问题

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

提示： 通过指定 fromIndex 去重

class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();public List<List<Integer>> combine(int n, int k) {helper(k,n, new LinkedList<Integer>(), 1);return res;}public void helper(int k, int n, LinkedList<Integer> path , int fromIndex){if(k == 0){res.add(new LinkedList(path));return;}for(int i = fromIndex; i <= n ;i ++){path.add(i);helper(k - 1, n, path, i +1);path.removeLast();}}
}

N皇后问题

n个皇后不冲突的放在n*n 的棋盘上

注意：对角线也不能重复

提示: 按行放置

class Solution {List<List<String>> res = new ArrayList<List<String>>();public List<List<String>> solveNQueens(int n) {char[][] path = new char[n][n];for(int i = 0; i < n;i++){for(int j= 0;j < n;j ++){path[i][j] = '.';}}helper(path, 0, n, new HashSet<Integer>(), new HashSet<Integer>(), new HashSet<Integer>());return res;}public void helper(char[][] path, int row, int n, Set<Integer> cols, Set<Integer> angles1, Set<Integer> angles2){if(row == n){List<String> tmp = new ArrayList<String>();for(int i = 0; i < n; i ++){StringBuilder sb = new StringBuilder();for(int j = 0; j < n; j ++){sb.append(path[i][j]);}tmp.add(sb.toString());}res.add(tmp);return;}for(int i = 0;i < n;i++){if(cols.contains(i)){// 纵向不能重复continue;}if(angles1.contains(row - i)){// 左上 - 右下 对角线不能重复continue;}if(angles2.contains(row + i)){// 左下 - 右上 对角线不能重复continue;}cols.add(i);angles1.add(row - i);angles2.add(row+i);path[row][i] = 'Q';helper(path, row+1, n, cols, angles1, angles2);cols.remove(i);angles1.remove(row - i);angles2.remove(row+i);path[row][i] = '.';}}
}

刷题

113.路径总和 II

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 思路：回溯算法，路径/当前可选择/选择及撤销选择

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();public List<List<Integer>> pathSum(TreeNode root, int sum) {List<Integer> path = new ArrayList<Integer>();if(root != null){path.add(root.val);}recurve(root, sum, path);return res;}public void recurve(TreeNode root, int sum, List<Integer> path){if(root == null){return;}if(root.left == null && root.right == null && sum == root.val){// 到叶子节点res.add(new ArrayList<Integer>(path));return;}if(root.left != null){path.add(root.left.val);recurve(root.left, sum - root.val, path);path.remove(path.size() - 1);}if(root.right != null){path.add(root.right.val);recurve(root.right, sum - root.val, path);path.remove(path.size() - 1);}}
}

31.下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

提示： 从后往前; 顺序对; 大于a的最小的数

class Solution {public void nextPermutation(int[] nums) {int i;for(i = nums.length-1; i>=1; i -- ){// 从后向前找第一个逆序对if(nums[i] > nums[i-1]){// 从后向前找到最小的比它大的数字for(int j = nums.length - 1; j >= i; j --){if(nums[j] >  nums[i - 1]){// 交换int tmp = nums[j];nums[j] = nums[i-1];nums[i - 1] = tmp;break; }}break;}}// 从i开始翻转排序for(int j = i, k = nums.length - 1; j < k; j ++,k--){int tmp = nums[j];nums[j] = nums[k];nums[k] = tmp;}}
}

47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[[1,1,2],[1,2,1],[2,1,1]
]

提示: 回溯,剪枝,数字次数

class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();public List<List<Integer>> permuteUnique(int[] nums) {Map<Integer, Integer> cnt = new HashMap<Integer, Integer>(); // 记录递归过程中哪些数字被用过了for(int i = 0; i < nums.length; i++){cnt.put(nums[i], cnt.getOrDefault(nums[i], 0) + 1);}LinkedList<Integer> path = new LinkedList<Integer>();helper(nums, path, cnt);return res;}public void helper(int[] nums, LinkedList<Integer> path, Map<Integer, Integer> cnt){if(path.size() == nums.length){res.add(new LinkedList(path));return;}Set<Integer> set = new HashSet<Integer>(); // 记录同一层有没有遍历过for(int i = 0; i < nums.length; i++){if(set.contains(nums[i])){continue; // 重复的数}if(cnt.get(nums[i]) == 0){continue; // 判断是否已经被用完}path.add(nums[i]);set.add(nums[i]);cnt.put(nums[i], cnt.get(nums[i]) - 1);helper(nums, path, cnt);path.removeLast();cnt.put(nums[i], cnt.get(nums[i]) + 1);}}
}

996. 正方形数组的数目

给定一个非负整数数组 A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。

返回 A 的正方形排列的数目。两个排列 A1 和 A2 不同的充要条件是存在某个索引 i，使得 A1[i] != A2[i]。

提示： 思路同上

class Solution {int res = 0;public int numSquarefulPerms(int[] A) {if(A.length == 0){return res;}Map<Integer, Integer> cnt = new HashMap<Integer, Integer>(); // 记录递归过程中哪些数字被用过了for(int i = 0; i < A.length; i++){cnt.put(A[i], cnt.getOrDefault(A[i], 0) + 1);}helper(A, cnt, -1, 0);return res;}public void helper(int[] nums, Map<Integer, Integer> cnt, int last, int used){if(used == nums.length){res++;return;}Set<Integer> set = new HashSet<Integer>(); // 记录同一层有没有遍历过for(int i = 0; i < nums.length; i++){if(set.contains(nums[i])){continue; // 重复的数}if(cnt.get(nums[i]) == 0){continue; // 判断是否已经被用完}if(last >= 0 && !isSquare(nums[i] + last)){continue; //判断是否符合题目条件}set.add(nums[i]);cnt.put(nums[i], cnt.get(nums[i]) - 1);used ++;helper(nums, cnt, nums[i], used );cnt.put(nums[i], cnt.get(nums[i]) + 1);used--;}}public boolean isSquare(int num){int i;for(i = 0; i*i < num; i++){}if(i * i == num){return true;}return false;}
}