网站云推广,golang 网站开发,wordpress 爱奇艺插件下载失败,常州网站建设怎么样题意理解#xff1a; 一个 无重复元素 的整数数组 candidates 和一个目标整数 target 从candidates 取数字#xff0c;使其和 target #xff0c;有多少种组合#xff08;candidates 中的 同一个 数字可以 无限制重复被选取#xff09; 这道题和之前一道组合的区别 一个 无重复元素 的整数数组 candidates 和一个目标整数 target 从candidates 取数字使其和 target 有多少种组合candidates 中的 同一个 数字可以 无限制重复被选取 这道题和之前一道组合的区别这道题允许重复的数字 解题思路 组合问题——递归 这道题特殊的地方对组合内数字的和做了要求而不是个数一开始并不确定树的深度组合的大小是不定的。 1.暴力回溯剪枝优化
class Solution {ListListInteger resultnew ArrayList();LinkedListInteger pathnew LinkedList();int sum0;public ListListInteger combinationSum(int[] candidates, int target) {backtracking(candidates,target,0);return result;}public void backtracking(int[] candidates,int target,int index){//结果收集if(sumtarget){result.add(new ArrayList(path));return;} else if (sumtarget) {//剪枝return;}//遍历分支for(int iindex;icandidates.length;i){path.add(candidates[i]);sumcandidates[i];//递归backtracking(candidates,target,i);//回溯path.removeLast();sum-candidates[i];}}
}
2.分析 时间复杂度O() n个位置每个位置有两种可能选或不选。 时间复杂度和树的深度有关是所有可行解之和 空间复杂度O(n)
