JAVA练习331- 组合总和
题目概览给你一个无重复元素的整数数组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来源39. 组合总和 - 力扣LeetCode解题分析方法回溯令当前索引为 i用集合 list 存储每次遍历得到的元素每次递归时遍历数组 candidates将元素加入 list 中然后 target - candidates[ i ]继续往下层遍历当 target 0 时存储 list 到最终结果中去当 target 0 时已没有可加的元素直接返回当 target 0 时继续重复以上操作遍历递归当下层遍历完成后将当前元素移除 list然后 target candidates[ i ]继续遍历下一个元素直到所有元素遍历完成返回结果。时间复杂度O(S) ( S 为所有可行解的长度之和 )空间复杂度O(target)class Solution { public ListListInteger combinationSum(int[] candidates, int target) { ListListInteger result new ArrayList(); backTracking(candidates, target, result, new ArrayList(), 0, candidates.length); return result; } public void backTracking(int[] candidates, int target, ListListInteger result, ListInteger list, int index, int n) { if (target 0) { result.add(new ArrayList(list)); return; } if (target 0) { return; } for (int i index; i n; i) { list.add(candidates[i]); target - candidates[i]; backTracking(candidates, target, result, list, i, n); list.remove(list.size()-1); target candidates[i]; } } }
)
