做外贸怎么找客户,网站做进一步优化,南宁3及分销网站制作,广州市番禺区回溯问题通常应用于解决排列组合等问题#xff0c;需要注意的是回溯函数中的参数、结束条件、遍历开始顺序等。 回溯三部曲#xff1a; #xff08;1#xff09;确定递归函数的参数。 #xff08;2#xff09;确定递归函数的终止条件。 #xff08;3#xff09;确定单层…回溯问题通常应用于解决排列组合等问题需要注意的是回溯函数中的参数、结束条件、遍历开始顺序等。 回溯三部曲 1确定递归函数的参数。 2确定递归函数的终止条件。 3确定单层搜索的逻辑。
1.全排列 题目链接
题目要求给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 代码及思路 使用回溯求排列回溯结束条件当前集合的元素个数等于nums数组中元素个数在回溯的每一层中选择当前未被使用的数字加入当前排列使用used数组记录已经使用过的元素代码
class Solution {ListListInteger resnew ArrayList();public ListListInteger permute(int[] nums) {boolean[] usednew boolean[nums.length];backTracing(nums,used,new ArrayList());return res;}private void backTracing(int[] nums,boolean[] used,ListInteger path){if(path.size()nums.length){res.add(new ArrayList(path));return;}for(int i0;inums.length;i){if(!used[i]){used[i]true;path.add(nums[i]);backTracing(nums,used,path);used[i]false;path.remove(path.size()-1);}}}
}2. 电话号码的字母组合 题目链接
题目要求给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 代码及思路 回溯的参数为输入字符串digits电话号码对应的字符串数组以及处理到digits中数字的顺序结束条件为但处理到的数字的顺序大于等于digits的长度时就可以添加到结果中并返回了回溯中循环直接从0开始因为这是在多个不同的字符串中进行组合不需要考虑重复问题代码
class Solution {ListString resnew ArrayList();public ListString letterCombinations(String digits) {if(digits.length()0)return res;String[] numbers{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};backTracing(digits,0,numbers);return res;}StringBuilder pathnew StringBuilder();private void backTracing(String digits,int start,String[] numbers){if(startdigits.length()){res.add(path.toString());return;}String strnumbers[digits.charAt(start)-0];for(int i0;istr.length();i){path.append(str.charAt(i));backTracing(digits,start1,numbers);path.deleteCharAt(path.length()-1);}}
}3. 路径总和 III回溯前缀和题目链接
题目要求给定一个二叉树的根节点 root 和一个整数 targetSum 求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。 代码及思路 因为每个节点都可能有左右节点因此需要回溯考虑多种情况使用前缀和来判断路径和代码
class Solution {public int pathSum(TreeNode root, int targetSum) {if(rootnull)return 0;MapLong,Integer presumnew HashMap();//注意主要是为了考虑从根节点开始到某个节点之间的路径刚好等于targetpresum.put(0L,1);return dfs(root,presum,0L,targetSum);}private int dfs(TreeNode root,MapLong,Integer presum,Long cur,int targetSum){if(rootnull)return 0;int res0;curroot.val;respresum.getOrDefault(cur-targetSum,0);presum.put(cur,presum.getOrDefault(cur,0)1);resdfs(root.left,presum,cur,targetSum);resdfs(root.right,presum,cur,targetSum);//回溯presum.put(cur,presum.get(cur)-1);return res;}
}4. 括号生成 题目链接
题目描述数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。 代码及思路 使用回溯解决问题递归时当当前字符串的长度等于n的两倍时添加到结果集中当左括号数量小于n时继续递归添加左括号当右括号数量小于左括号数量时递归添加右括号代码
class Solution {ListString resnew ArrayList();public ListString generateParenthesis(int n) {backTracing(,0,0,n);return res;}private void backTracing(String cur,int left,int right,int n){if(cur.length()2*n){res.add(cur);}if(leftn){backTracing(cur(,left1,right,n);}if(rightleft){backTracing(cur),left,right1,n);}}}5. 子集 题目链接
题目要求给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 代码及思路 使用回溯解决问题每次递归时起始位置加1避免元素重复每一次递归过程都将当前的路径集合加入结果集当path的长度等于数组的个数时结束递归代码
class Solution {ListListInteger resnew ArrayList(); public ListListInteger subsets(int[] nums) {backTracing(nums,0,new ArrayList());return res;}private void backTracing(int[] nums,int start,ListInteger path){res.add(new ArrayList(path));if(startnums.length){return;}for(int istart;inums.length;i){path.add(nums[i]);backTracing(nums,i1,path);path.remove(path.size()-1);}}}6. 组合总数 题目链接
题目要求给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。 对于给定的输入保证和为 target 的不同组合数少于 150 个。 代码及思路 使用回溯解决每次回溯的起始位置都是当前遍历的元素当target刚好等于0的时候将当前结果加入结果集并结束递归当target小于0时结束递归代码
class Solution {ListListInteger resnew ArrayList();public ListListInteger combinationSum(int[] candidates, int target) {backTracing(candidates,0,target,new ArrayList());return res;}private void backTracing(int[] candidates,int start,int target,ListInteger path){if(target0){res.add(new ArrayList(path));return;}if(target0){return;}for(int istart;icandidates.length;i){path.add(candidates[i]);backTracing(candidates,i,target-candidates[i],path);path.remove(path.size()-1);}}
}7.目标和 题目链接
题目要求给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 ‘’ 或 ‘-’ 然后串联起所有整数可以构造一个 表达式 例如nums [2, 1] 可以在 2 之前添加 ‘’ 在 1 之前添加 ‘-’ 然后串联起来得到表达式 “2-1” 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 代码及思路 使用回溯来解决问题首先对每一个数字可能添加的不同符号进行考虑并对每一种情况进行递归每一个数字的返回结果是两种不同符号的和递归结束条件遍历到数组结束代码
class Solution {public int findTargetSumWays(int[] nums, int target) {return backTracing(nums,target,0,0);}private int backTracing(int[] nums, int target, int index, int currentSum) {if (index nums.length) {// 当遍历完所有的数字后判断当前的和是否等于目标值return currentSum target ? 1 : 0;}// 选择将当前数字添加正号int add dfs(nums, target, index 1, currentSum nums[index]);// 选择将当前数字添加负号int subtract dfs(nums, target, index 1, currentSum - nums[index]);// 返回两种选择的总和return add subtract;}
}
