视频链接:https://www.bilibili.com/video/BV1yh411m7Yn/?spm_id_from=333.337.search-card.all.click&vd_source=09ee57e950c1151087156a55e2d0aa26
回溯算法的基本过程:进行选择,递归,撤回选择
一般采用深度优先,共有4钟剪枝策略
策略一:每个元素只能使用一次 方法——用used数组剪枝 实例:leetcode46
public static void dfs(int[] nums, List<Integer> path, boolean[] used){ if(path.size()==nums.length){ list2.add(new ArrayList<>(path)); return; } for(int i=0;i<nums.length;i++){ if(used[i]==true){ continue; } used[i]=true; path.add(nums[i]); dfs(nums,path,used); used[i]=false; path.remove(path.size()-1); } }
剪枝策略二:全排列时给定的数组有重复数字 方法——把当前层重复的枝头剪掉 实例:leetcode47
class Qpl{ public List<List<Integer>> search(int[] nums){ Arrays.sort(nums); List<List<Integer>> res=new ArrayList<List<Integer>>(); List<Integer> path=new ArrayList<Integer>(); boolean[] used=new boolean[nums.length]; dfs(nums,res,path,used); return res; } public void dfs(int[] nums,List<List<Integer>> res,List<Integer> path, boolean[] used){ if(path.size()==nums.length){ res.add(new ArrayList<Integer>(path)); return; } for(int i=0;i<nums.length;i++){ if(used[i]){ continue; } if(i>0 && nums[i-1]==nums[i] && !used[i-1]){ continue; } used[i]=true; path.add(nums[i]); dfs(nums,res,path,used); used[i]=false; path.remove(path.size()-1); } } }
剪枝策略三:给定target,要凑出来和等于它的元素 方法——for循环中一旦看到大于target,直接停止i++,同时要进行排序。
class Zh{ public List<List<Integer>> search(int[] nums,int target){ Arrays.sort(nums); List<List<Integer>> res=new ArrayList<List<Integer>>(); List<Integer> output=new ArrayList<Integer>(); dfs(res,output,nums,target,0,0); return res; } public void dfs(List<List<Integer>> res,List<Integer> output,int[] nums, int target,int sum,int start){ if(sum==target){ res.add(new ArrayList<Integer>(output)); return; } for(int i=start;i<nums.length;i++){ if(sum+nums[i]>target){ break; } output.add(nums[i]); dfs(res,output,nums,target,sum+nums[i],i); output.remove(output.size()-1); }
剪枝策略四:对于组合问题,[1,1,6] target是8 输出的数组元素不能重复 如[1,1,6]和[1,6,1]就是重复的数组 方法——在循环时候起始位置为start 实例40组合|| 这个问题包含了以上四种剪枝策略,数组中的元素不能重复使用,[1,3,2] [1,2,3]不能同时出现,这两个问题可以通过for循环中起始位置是start解决,如果数组中出现了重复的元素,[1,1,6] 结果中[1,1,6][1,1,6]不能同时出现,这个就通过nums[i-1]=nums[i] && nums[i]=false进行判断剪枝 当sum>target时,就break
class Zh2{ public List<List<Integer>> search(int[] nums,int target){ Arrays.sort(nums); List<List<Integer>> res=new ArrayList<List<Integer>>(); List<Integer> output=new ArrayList<Integer>(); dfs(res,output,nums,target,0,0); return res; } public void dfs(List<List<Integer>> res,List<Integer> output,int[] nums,int target,int sum,int start){ if(sum==target){ res.add(new ArrayList<Integer>(output)); return; } for(int i=start;i< nums.length;i++){ if(sum+nums[i]>target){ break; } if(i>start && nums[i-1]==nums[i]) { continue; } output.add(nums[i]); dfs(res,output,nums,target,sum+nums[i],i+1); output.remove(output.size()-1); } } }
标签:target,nums,int,res,List,算法,回溯,output From: https://www.cnblogs.com/zhang12345/p/16767153.html