上海高端网站开发站霸网络,wordpress添加首页,泉州做网站企业,律师网站建设模板题意理解#xff1a; 每个数字在每个组合中只能使用 一次 数字可以重复——难点#xff08;如何去重#xff09; 每个组合和target 求组合#xff0c;对合限制#xff0c;考虑回溯的方法。——将其抽象为树结构。 树的宽度——分支大小 树的深度——最… 题意理解 每个数字在每个组合中只能使用 一次 数字可以重复——难点如何去重 每个组合和target 求组合对合限制考虑回溯的方法。——将其抽象为树结构。 树的宽度——分支大小 树的深度——最长的组合和target 去重难点 根据《代码随想录》关于树层去重的引入 第一个位置选2再次选2的话下面的分支回出现重复的[2,3]组合。 实际上保留第一个分支之后同一位置相同的数值选项可以剪除。 用used[]数组来维护是否被访问的状态。 回溯的方法 1.确定返回值参数列表 2.确定终止条件|剪枝条件 3.单层逻辑|回溯操作 1.暴力回溯剪枝优化
考虑返回值一般为void, 参数包含数组和目标值当前数值指示下标
终止条件 sum4,特别的sum4时收集结果。
单层递归逻辑一定要对sum和path、used数组做好回溯操作。
数层剪枝candidates[i-1]candidates[i]遇到重复值 used[i-1]true:表示上一个重复的值在该组合内被用到。 used[i - 1] false表示上一个重复值在该组合内没有用到应该是同一树层用到——即数层重复剪枝。
ListListInteger resultnew ArrayList();LinkedListInteger pathnew LinkedList();int sum0;public ListListInteger combinationSum2(int[] candidates, int target) {boolean[] usednew boolean[candidates.length];Arrays.sort(candidates);Arrays.fill(used, false);backtrackig(candidates,target,0,used);return result;}public void backtrackig(int[] candidates, int target,int startIndex,boolean[] used){//终止|剪枝if(sumtarget) return;else if (sumtarget) {result.add(new ArrayList(path));return;}//单层递归逻辑for(int istartIndex;icandidates.length;i){//数层剪枝if(i!0candidates[i-1]candidates[i]used[i-1]false) continue;path.add(candidates[i]);sumcandidates[i];used[i]true;backtrackig(candidates,target,i1,used);path.removeLast();sum-candidates[i];used[i]false;}}
注意两个特殊的地方
Arrays.sort(candidates);//数组排序
Arrays.fill(used, false);//数组填充实际上该数组默认也是false.
2.分析 时间复杂度O() 空间复杂度O(n)
