摘要:和唯一的不同是组合中不能存在重复的元素,因此,在递归时将初始位即可。
Combination Sum I Problem
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
NoticeAll numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]
基本思路与Combinations一致,递归模板详见:https://segmentfault.com/a/11...
有两个点需要注意:在组合中的数必须是升序排列,所以在调用dfs函数之前要先排序;另外,由于组合里允许有重复数,dfs调用自身时,初始位start(=i)的位置不变,依然从i开始,只需将target减小num[i]即可。
public class Solution { ListCombination Sum II Problem> res = new ArrayList<>(); public List
> combinationSum(int[] candidates, int target) { Arrays.sort(candidates); helper(candidates, 0, target, new ArrayList
()); return res; } public void helper(int[] c, int start, int t, List pre) { if (t < 0) return; if (t == 0) res.add(pre); for (int i = start; i < c.length; i++) { List cur = new ArrayList (pre); cur.add(c[i]); helper(c, i, t-c[i], cur); } } }
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
NoticeAll numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
Given candidate set [10,1,6,7,2,1,5] and target 8,
A solution set is:
[
[1,7],
[1,2,5],
[2,6],
[1,1,6]
]
和Combination Sum I唯一的不同是组合中不能存在重复的元素,因此,在dfs递归时将初始位+1即可。
Solutionpublic class Solution { List> res = new ArrayList
>(); public List
> combinationSum2(int[] num, int target) { Arrays.sort(num); helper(num, 0, target, new ArrayList
()); return res; } public void helper(int[] num, int start, int target, List pre) { if (target < 0) return; if (target == 0) { res.add(pre); return; } for (int i = start; i < num.length; i++) { if (i > start && num[i] == num[i-1]) continue; List cur = new ArrayList (pre); cur.add(num[i]); helper(num, i+1, target-num[i], cur); } } }
Combination Sum III & IV link: here
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65721.html
Subsets Problem Given a set of distinct integers, return all possible subsets. Notice Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. Example ...
摘要:整个过程相当于,直接在和里去掉既是又是的。所以最后返回的,一定是只出现过一次的,而出现两次的都在里,出现三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...
摘要:建立动规数组,表示从起点处到达该点的可能性。循环结束后,数组对所有点作为终点的可能性都进行了赋值。和的不同在于找到最少的步数。此时的一定是满足条件的最小的,所以一定是最优解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...
摘要:和完全一样的做法,只要在初始化首行和首列遇到时置零且即可。对了,数组其它元素遇到也要置零喏,不过就不要啦。 Problem Follow up for Unique Paths: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle...
Problem Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at ...
阅读 2692·2023-04-25 19:13
阅读 4009·2021-09-22 15:34
阅读 3052·2019-08-30 14:23
阅读 1461·2019-08-29 17:17
阅读 1603·2019-08-29 16:05
阅读 1537·2019-08-29 13:26
阅读 1217·2019-08-29 13:19
阅读 553·2019-08-29 13:16