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 <= 30
• 2 <= candidates[i] <= 40
• candidates的所有元素互不相同
• 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 List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> result = new ArrayList<>(); backTracking(candidates, target, result, new ArrayList<>(), 0, candidates.length); return result; } public void backTracking(int[] candidates, int target, List<List<Integer>> result, List<Integer> 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]; } } }