网站建设资讯平台,网站建设-丹东,苏州网站建设姜超,企业电子商务网站开发39. 组合总和
解题思路
改造回溯算法找到目标和之后 本次回溯结束 添加路径记录遍历数组 选择路径 回溯 撤销选择
class Solution {ListListInteger res new LinkedList();LinkedListInteger track new LinkedList();// 记录路经…39. 组合总和
解题思路
改造回溯算法找到目标和之后 本次回溯结束 添加路径记录遍历数组 选择路径 回溯 撤销选择
class Solution {ListListInteger res new LinkedList();LinkedListInteger track new LinkedList();// 记录路经综合int trackSum 0;public ListListInteger combinationSum(int[] candidates, int target) {// 每一个元素被反复使用 将i 1 改成i即可// 相当于给之前的回溯树添加一条树枝 遍历这棵树的过程中 一个元素可以被无限次使用if(candidates.length 0){return res;}backtrack(candidates,0,target);return res;}//回溯算法主函数void backtrack(int[] nums,int start,int target){if(trackSum target){// 找到目标和 本次回溯结束res.add(new LinkedList(track));return;}//base caseif(trackSum target){return;}// 回溯算法 标准框架for(int i start; i nums.length; i){// 选择nums[i]trackSum nums[i];track.add(nums[i]);backtrack(nums,i,target);// 撤销选择trackSum - nums[i];track.removeLast();}}
}
