温州专业微网站制作,文登做网站的公司,网站图片管理系统,教务管理系统登录入口回溯算法解题思路回溯的两种思路题目描述按照思路1解决按思路2解决回溯的两种思路
看不同的解题方法#xff0c;形成不同的思维。 先说结论。回溯解题思路1#xff1a;是对可选择每个元素#xff0c;采取不选择、选择两种策略#xff0c;不断递归下去。最近看花花酱的视频…
回溯算法解题思路回溯的两种思路题目描述按照思路1解决按思路2解决回溯的两种思路
看不同的解题方法形成不同的思维。 先说结论。回溯解题思路1是对可选择每个元素采取不选择、选择两种策略不断递归下去。最近看花花酱的视频得到思路2要完成目标分为n个阶段每个阶段会有不同的选择在每个阶段尝试不同选择。 下面以具体leetcode39为例来说明。
题目描述
输入一个不包含重复元素的数组candidates一个int target 输出用candidates中的元素组成target输出有多少种组合。输出结果不能重复。 规则candidates中的元素可以使用多次。 例如candidates[2,3,6,7] target7返回 [ [7], [2, 2, 3] ]
按照思路1解决
结果集是包含多种解法用ListList result 表示。每一种解法是一个List list。 对于候选数组candidates中的每个元素我们可能使用也可能不使用。 例如对于index 0我们可能使用candidates[0]也可能不使用。 不使用candidates[0]target不变list不变index1进入选择candidates[1]阶段。 使用candidates[0]target变小list添加使用candidates[0]index1进入选择candidates[1]阶段。注意因为题目说一个元素可以重复使用那candidates[0]最多可以使用target/candidates[0]次。
在代码中使用path记录每个元素选择多少次。path[0]candidates[0]选择的次数。 退出条件当target0问题解决添加结果集。下标超出范围的时候或者target0退出循环。 private ListListInteger result new ArrayListListInteger();private int[] path;private int[] candidates;/*** path[i] 使用nums[i]元素的次数* param candidates* param target* return*/public ListListInteger combinationSumV2(int[] candidates, int target) {result.clear();path new int[candidates.length];this.candidates candidates;dfsV2(0, target);return result;}private void dfsV2(int idx, int target) {if (target 0) {ListInteger solution new ArrayListInteger();for (int i 0; i path.length; i) {for (int j 1; j path[i]; j) {solution.add(candidates[i]);}}result.add(solution);return;}if (idx candidates.length || target 0) {return;}int maxCount target / candidates[idx];for (int i 0; i maxCount; i) {path[idx] i;dfsV2( idx 1, target - i * candidates[idx]);path[idx] 0;}}按思路2解决
target7可以选择2367任意一个元素也就是candidates中下标从0到4的任意一个元素。选择2list添加2进入状态target5。 target5可以选择23。因为67大于5不用选择剪枝。选择2list添加2进入target3。 target3可以选择2,3。因为67大于3不用选择剪枝。选择2list添加2进入target1。 … 退出条件当target0问题解决添加结果集。
按照这个思路画递归树发现有重复的解。可以通过限制下标起点解决。例如图中选择3之后可以选择的元素就在367之间因为367都大于2所以就不用继续递归了。所以递归树上的状态需要加上起始下标。修改递归树。 public ListListInteger combinationSumV3(int[] candidates, int target) {result.clear();Arrays.sort(candidates);this.candidates candidates;if(candidatesnull || candidates.length0) return result;dfsV3(0,target,new ArrayListInteger());return result;}/*** 在当前状态下可以选择从start到数组结尾的任意一个元素到结果集** param start* param target* param list*/private void dfsV3(int start, int target,ArrayListInteger list) {if(target 0) {//注意结果需要完全拷贝result.add(new ArrayListInteger(list));return;}if(start candidates.length) return;for(int i start;icandidates.length;i){if(candidates[i] target) break;list.add(candidates[i]);dfsV3(i,target-candidates[i],list);list.remove(list.size() - 1);}}每一次dfs是树的一个高度。
