男男做受网站,网站开发网站源码,做英文简历的网站,mysql 网站 数据库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 。
仅有这两种组合。
示例 2
输入: candidates [2,3,5], target 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3
输入: candidates [2], target 1
输出: []
这道题我用递归写的当然我觉得递归绝对不算是最优解。因为这道题目与一般递归的不同在于它的数字可以重复出现但是相同元素的数组却不能重复出现这就导致一个问题即我们不能通过标记该数字是否出现来进行排除因为所有数字都有可能再度被引用而不能排除则会导致重复数组的出现如第一个例子中会出现223以及232的重复答案。
要解决这个问题最好的办法就是先进行排序ps.数组先排序在绝大多数情况都能大大简化骤然后记录每一步的开始位置例如循环从2开始则下一步的递归也从2开始。因为我们已经将数组排序好了所以所有已经过循环的数字都可以确定为不会再使用。
class Solution {public ListListInteger combinationSum(int[] candidates, int target) {ListListInteger list new ArrayList();StackInteger stack new Stack();Arrays.sort(candidates);dfs(list,stack,candidates,target,0);return list;}public static void dfs(ListListInteger list, StackInteger stack,int[] nums,int target,int begin){int temp target;if (temp0){list.add(new ArrayList(stack));return;}for (int ibegin;inums.length;i){if(temp-nums[i]0)break;temptemp-nums[i];stack.push(nums[i]);if (temp0){dfs(list,stack,nums,temp,i);}stack.pop();tempnums[i];}}
}
