富阳市网站,wordpress知更鸟打赏,周口建设企业网站公司,网页设计公司企业组织结构图文章目录题目描述思路 代码题目描述
讲道理#xff0c;像这种找可行集合解的问题#xff0c;基本上都可以通过回溯 剪枝来做
思路 代码
sort()用于优化#xff0c;多一个剪枝判断#xff0c;其实也可以不写双向队列deque#xff1a;第一次用#xff0c;…
文章目录题目描述思路 代码题目描述
讲道理像这种找可行集合解的问题基本上都可以通过回溯 剪枝来做
思路 代码
sort()用于优化多一个剪枝判断其实也可以不写双向队列deque第一次用队列、栈肯定不能用因为既有先进先出要求又有先进后出要求removeLast 用于构造ArrayList数组可以但是要多传一个下标值比较麻烦。用nowIndex来保证不会重复相当于从左到右遍历所有结果而不重复遍历deque只用一条就够了在回溯过程中不断调整内容。nowNum target的情况直接剪枝即可已经没有继续走的必要了
class Solution {public ListListInteger combinationSum(int[] candidates, int target) {// 基于排序后的优化剪枝做法ListListInteger ans new ArrayList();// 使用一个双向队列DequeInteger path new ArrayDeque();// 回溯 双向队列Arrays.sort(candidates);back(candidates,0,target,0,path,ans);return ans;}// 找到正确结果后一个个回去// 不重复用nowIndex保证void back(int[] candidates, int nowNum, int target, int nowIndex, DequeInteger path,ListListInteger ans){// 剪枝if(nowNum target){return;}// 找到了else if(nowNum target){ans.add(new ArrayList(path));return;}// 小于else{for(int i nowIndex; i candidates.length; i){// 因为排序过了所以此处可以剪枝if(nowNum candidates[i] target){return;}path.addLast(candidates[i]);back(candidates, nowNum candidates[i], target, i, path, ans);path.removeLast();}}}
}
