39. 组合总和

题目描述 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明: 所有数字(包括 target)都是正整数。 解集不能包含重复的组合。  示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ] 示例 2: 输入: candidates = [2,3,5], target = 8, 所求解集为: [   [2,2,2,2],   [2,3,3],   [3,5] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/combination-sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 在上一篇文章“代码模版-排列与组合”我们介绍了排列与组合的实现方法,在这道题中,我们将会在组合算法上进行一些修改来解这道题目。我们先观察下组合算法的实现。 在这道题目中,要求数字可以重复选取,但是上面的代码每次都会选取新的一个数字。我们将递归调用combination(arr, depth + 1, i + 1, curr, result)改成combination(arr, depth + 1, i, curr,…

Read more

代码模版 – 排列与组合

有的时候题目想不出来,或者只能用搜索来解决(如Leetcode – 39题),我们就可以用排列/组合搜索答案。下面的排列与组合模板都使用DFS来实现,非常易懂且方便记忆。 1. 排列 方法private void permutation(int[] arr, int depth, int[] curr, boolean[] visited, List<int[]> result)实现了求arr的所有排列,并且将结果保存的result中。depth表示目前正在填充curr的第几位,visited数组记录了之前已经访问的元素。在for循环中,我们遍历每个之前没有访问过位置,并在visited标记为true,防止下一次递归调用访问同一元素。当depth达到数组arr的长度时,我们复制curr的内容到result中。 2. 组合 这里的组合指的是从n个元素中挑选c个元素,而不考虑元素的顺序。方法void combination(int[] arr, int depth, int start, int[] curr, List<int[]> result)实现了从arr中挑选|curr|个元素。depth表示我们正在填充curr的第几位,start参数表明我们从arr中第几个位置开始挑选元素。与排列算法相比,我们不需要visited数组。因为我们总是从start之后挑选元素,所以不会出现挑选重复元素的情况。

Read more