LeetCode39.组合总和

给你一个无重复元素的整数数组candidates和一个目标整数target找出candidates中可以使数字和为目标数target的 所有不同组合并以列表形式返回。你可以按任意顺序返回这些组合。candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同则两种组合是不同的。对于给定的输入保证和为target的不同组合数少于150个。示例 1输入candidates [2,3,6,7], target 7输出[[2,2,3],[7]]解释2 和 3 可以形成一组候选2 2 3 7 。注意 2 可以使用多次。 7 也是一个候选 7 7 。 仅有这两种组合。示例 2输入:candidates [2,3,5], target 8输出:[[2,2,2,2],[2,3,3],[3,5]]示例 3输入:candidates [2], target 1输出:[]提示1 candidates.length 302 candidates[i] 40candidates的所有元素互不相同1 target 40解题思路首先组合题考回溯算法但这和普通的组合有什么特殊的地方1.同一个数字可以无限取2.不同组合这两个限制条件就是这道题的切入点回溯三件套确定方法参数我们需要用来传递数组题目提供的数组是一个参数还有就是targetstartIndex需不需要是需要的因为我们要确定每一个组合是唯一的所以要从当前Index向后遍历最后就是sum。确定终止条件因为没有元素个数的限制所以只有两种情况终止一是sum大于target二是sum等于target。确定单层循环逻辑for(int istartIndex;icandidates.length;i){ int valuecandidates[i]; if(sumvaluetarget){ break; } tmp.add(value); backtracking(candidates,target,sumvalue,i); tmp.removeLast(); }代码class Solution { private ListListInteger resultnew ArrayList(); private ListInteger tmpnew LinkedList(); public ListListInteger combinationSum(int[] candidates, int target) { if(candidatesnull||candidates.length0) return result; Arrays.sort(candidates); backtracking(candidates,target,0,0); return result; } public void backtracking(int[] candidates,int target,int sum,int startIndex){ if(sumtarget){ return; } if(sumtarget){ result.add(new ArrayList(tmp)); return; } for(int istartIndex;icandidates.length;i){ int valuecandidates[i]; if(sumvaluetarget){ break; } tmp.add(value); backtracking(candidates,target,sumvalue,i); tmp.removeLast(); } } }