回溯算法的框架:
result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择
Attention: 注意“全排列”和“所有子集”中backtrack()的参数区别。
LeetCode 46 - 全排列
class Solution { public List<List<Integer>> permute(int[] nums) { //暂存结果 ArrayList<Integer> track = new ArrayList<>(); //最终结果 List<List<Integer>> result = new ArrayList<>(); //回溯函数 backtrack(nums, track, result); return result; } private void backtrack(int[] nums, ArrayList<Integer> track, List<List<Integer>> result){ //end condition if(track.size() == nums.length){ result.add(new ArrayList(track)); return; } //【重要】每次索引都从0开始!!!这里和“所有子集”问题不同 for(int i = 0; i < nums.length; i++){ //用contains判断是否存在 if(! track.contains(nums[i])){ track.add(nums[i]); backtrack(nums, track, result); //删除容器里,最后一个索引的值 track.remove(track.size()-1); } } } }
Leetcode 78 - 子集
class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); List<Integer> track = new ArrayList<>(); backtrack(nums, 0, track, res); return res; }
//【重要】注意这个参数start private void backtrack(int[] nums, int start, List<Integer> track, List<List<Integer>> res){ //每一个路径,都是一个解 //【重要】这里没有明显的一个递归出口,而是靠下面的for循环的终止条件 //【重要】因为track是公用的,所以在加入res前,需要复制一份新的 res.add(new ArrayList(track));
//每次递归不是从0开始,而是start for(int i = start; i < nums.length; i++){ //重要】i 已经放在了track暂时解中,因此在此前提下,之后的递归就要exclude这个i,那就i+1即可 track.add(nums[i]); //System.out.println("track add " + nums[i]); backtrack(nums, i+1, track, res); track.remove(track.size() - 1); } } }
原文:https://www.cnblogs.com/frankcui/p/13833204.html