方案库网站,开淘宝店怎么做充值网站,国内看网站 优帮云,7万字短篇小说哪家网站做的好39. 组合总和
给你一个无重复元素的整数数组candidates和一个目标整数target #xff0c;找出candidates中可以使数字和为目标数target的 所有不同组合#xff0c;并以列表形式返回。你可以按**任意顺序 **返回这些组合。
candidates中的同一个数字可以 无限制重复被选取 。…39. 组合总和
给你一个无重复元素的整数数组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 。 仅有这两种组合。
题目分析 回溯法解题步骤
针对所给问题定义问题的解空间确定易于搜索的解空间结构以深度优先方式搜索解空间并在搜索过程中用剪枝函数避免无效搜索 回溯法有“通用解题法”之称用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。 详细可见 Leetcode 回溯法详解 经典排列树按节点遍历更多案例可见 Leetcode 回溯法详解
class Solution {ListListInteger res new ArrayList();public ListListInteger combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backtrack(candidates, 0, new ArrayList(), target);return res;}/*** output(x) 记录或输出得到的可行解x* constraint(t) 当前结点的约束函数* bount(t) 当前结点的限界函数* param t t为当前解空间的层数*/private void backtrack(int[] nums, int k, ListInteger temp, int target) {// bountif (target 0) {res.add(new ArrayList(temp));return;} else if (target 0) {return;}for (int i k; i nums.length; i) {// 剪枝if (target - nums[i] 0) {break;}temp.add(nums[i]);backtrack(nums, i, temp, target - nums[i]);temp.remove(temp.size() - 1);}}
}
