张家港保税区规划建设局网站,深圳网站建设_,西安微信网站建设,wordpress调用分类标题文章目录 题目方法一#xff1a;递归回溯 题目 这题的nums数组里面不存在重复元素#xff0c;所以也就无需做去重操作 但同一个元素可以被无限次取#xff0c;说明每次递归中的for循环的开始位置就是自己
nums数组里面存在重复元素#xff0c;去重版本#xff1a;
方法一… 文章目录 题目方法一递归回溯 题目 这题的nums数组里面不存在重复元素所以也就无需做去重操作 但同一个元素可以被无限次取说明每次递归中的for循环的开始位置就是自己
nums数组里面存在重复元素去重版本
方法一递归回溯
参考讲解视频带你学透回溯算法-组合总和对应「leetcode」力扣题目39.组合总和| 回溯法精讲 ListListInteger res new ArrayList();//最终结果集int len 0;//数组长度public ListListInteger combinationSum(int[] candidates, int target) {Arrays.sort(candidates);//对数组排序 方便后面做剪枝len candidates.length;ListInteger zres new ArrayList();//子结果集int sum 0; //初始为0int startIndex 0; //设置标志位 使得每次只能取自己和自己之后的数组成子结果 避免重复子集dfsback(candidates,zres,sum,target,startIndex);return res;}public void dfsback(int[]candidates, ListInteger zres,int sum,int target,int startIndex){if(sum target){res.add(new ArrayList(zres));//如果sum target 收获节点的子集合 再往下遍历肯定大于target 所以直接returnreturn;}if(sum target) return; //如果sum大于target 后面就无需遍历了for(int i startIndex ; i len ;i){//题目说同一个 数字可以 无限制重复被选取 那每次遍历都可以从他自己startIndex开始取到数组尾吧一般都是i1后面取sum candidates[i];zres.add(candidates[i]);dfsback(candidates,zres,sum,target,i);//往下递归 这里的i是为了 往下面递归不能取数组前面 的数不然会出现重复子集 [2,2,3],[2,3,2],[3,2,2]sum - candidates[i];//回溯复原原值zres.remove(zres.size()-1);}
