LeetCode回溯算法的解题思路

回溯法概念

回溯法：一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。

应用场景

回溯算法可以搜索得到所有的方案，本质上它是一种穷举算法。

回溯法的原理

回溯算法 = dfs+剪枝

dfs:深度优先遍历，从最上层逐步往下遍历，会用到递归。
剪枝，就是去掉不符合条件的分支。

回溯算法的框架

回溯算法其实是树形问题上的深度优先遍历.
其核心就是 for 循环里面的递归，在递归调用之前「选择元素」，在递归调用之后「撤销选择元素」。

def backtrack(已添加数据的集合, 可选的元素列表):if 满足结束条件:result.add(已添加数据的集合)returnfor 元素 in 可选的元素列表:选择元素backtrack(已添加数据的集合, 可选的元素列表)撤销选择元素

LeetCode46，全排列。

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

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

LeetCode78.子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：
输入：nums = [0]
输出：[[],[0]]

public class LeetCode78 {public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> resultList= new ArrayList<>();backTrack(0, nums, resultList, new ArrayList<>());return resultList;}/*** 回溯法进行穷举**/public void backTrack(int i, int[] nums, List<List<Integer>> resultList, List<Integer> tmp) {//添加子集resultList.add(new ArrayList<>(tmp));for(int j=i;j<nums.length;j++) {//添加选择的元素tmp.add(nums[j]);//递归， 子集的下标从j+1开始遍历backTrack(j+1, nums, resultList, tmp);//回溯，撤消选择tmp.remove(tmp.size()-1);}}}

LeetCode22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2：
输入：n = 1
输出：[“()”]

提示： 1 <= n <= 8

public class LeetCode22 {/*** 生成 n 个括号()* @param n 括号的数量* @return*/public List<String> generateParenthesis(int n) {List<String> resultList = new ArrayList<>();if (n == 0) {return resultList;}//深度优先遍历dfs("", n, n, resultList);return resultList;}/**** 深度优先遍历，每往下遍历一次，减少一个左括号，或者右括号** @param s 当前递归得到的结果* @param left 剩余的左括号数量* @param right 剩余的右括号数量* @param resultList 结果集*/private void dfs(String s, int left, int right, List<String> resultList) {//左右括号都用完了，就说明满足条件，可以加入到结果集中if (left == 0 && right == 0) {resultList.add(s);}//回溯算法=dfs+剪枝.//剪枝，就是去掉不符合条件的分支。//如果剩余的左括号数量大于剩余的右括号数量，说明是不符合条件的。比如 )))(if (left > right) {return;}//使用左括号，左括号的数量减一if (left > 0) {dfs(s+"(", left-1, right, resultList);}//使用右括号，右括号的数量减一if (right > 0) {dfs(s+")", left, right-1, resultList);}}
}

详情参考：

https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-xiang-jie-by-labuladong-2/