摘要:解题思路对数组进行排序,每次加入第个数后,就减去这个数,并作为新的,进行递归。如果,则说明本次无解如果,则将本序列组合加入结果集中。题意其实就是从数组中选出个数,使得等于。
Combination Sum
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.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is: [ [7], [2, 2, 3] ]
1.解题思路
对数组进行排序,每次加入第i个数后,target就减去这个数,并作为新的target,进行递归。如果target<0,则说明本次无解;如果target=0,则将本序列组合加入结果集中。因为数字可以repeated,所以每次递归都从第i个开始。
2.代码
public class Solution { List> res=new ArrayList
>(); public List
> combinationSum(int[] candidates, int target) { if(candidates.length==0) return res; Arrays.sort(candidates); combine(candidates,target,0,new ArrayList
()); return res; } private void combine(int[] candidates, int target, int index,List pre){ if(target<0) return; if(target==0){ res.add(pre); return; } for(int i=index;i cur=new ArrayList (pre); cur.add(candidates[i]); combine(candidates,target-candidates[i],i,cur); } } }
Combination Sum II
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.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
1.解题思路
本题与上一题的区别就是同一个数字在一个组合中只能出现一次,那么就需要考虑下面两种情况:
1) 每次递归开始的index要加1;
2)在同一个for循环中,即针对同一个target,需要排除重复的数字。因为数组已经事先进行排序,所以只要判断下当前数字是否和前一个数字相等即可。
2.代码
public class Solution { List> res=new ArrayList
>(); public List
> combinationSum2(int[] candidates, int target) { if(candidates.length==0) return res; Arrays.sort(candidates); combineHelper(candidates,0,target,new ArrayList
()); return res; } private void combineHelper(int[] candidates,int index,int target,List pre){ if(target<0) return; if(target==0){ res.add(pre); return; } for(int i=index;i index&&candidates[i]==candidates[i-1]) continue; List cur=new ArrayList (pre); cur.add(candidates[i]); combineHelper(candidates,i+1,target-candidates[i],cur); } } }
Combination Sum III
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1: Input: k = 3, n = 7 Output: [[1,2,4]] Example 2: Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]]
1.解题思路
其实本题与题I非常相似,只是加入了组合元素的个数限制k。题意其实就是从数组[1,2,...,9]中选出k个数,使得sum等于target。唯独一点与题I的区别就是这里每个数只能选一遍,所以每次递归都从i+1开始。
2.代码
public class Solution { List> res =new ArrayList
>(); public List
> combinationSum3(int k, int n) { if(k==0||n==0) return res; int[] nums={1,2,3,4,5,6,7,8,9}; combine(nums,0,n,k,new ArrayList
()); return res; } private void combine(int[] nums,int index,int target,int k,List pre){ if(target<0) return; if(target==0&&k==0){ res.add(pre); return; } for(int i=index;i cur=new ArrayList (pre); cur.add(nums[i]); combine(nums,i+1,target-nums[i],k-1,cur); } } }
Combination Sum IV
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
nums = [1, 2, 3] target = 4 The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations. Therefore the output is 7.
1.解题思路
受前面三题的启发,很容易就想到继续用递归进行回溯,但是发现Time Exceed Limit. 再仔细看题目,发现其实是动态规划。给定一个数组,求和为target的组合个数,那我们定义状态dp[i]表示和为i的数字组合的个数,那么状态转移就是dp[i]=dp[i-nums[0]]+dp[i-nums[1]]+...+dp[i-nums[n-1]];当然前提是i大于nums[]。
其实说到这,我们发现这其实和动态规划的经典题目CoinChange找零钱非常相似,但找零钱相对复杂一些,因为找零钱需要得到所有组合中拥有最少元素的组合的元素数量,即最少的纸币数目;但这一题只需要求出所有的组合数即可。
CoinChange可参考 https://segmentfault.com/a/11...
2.代码
public class Solution { public int combinationSum4(int[] nums, int target) { if(nums.length==0||target==0) return 0; int[] dp=new int[target+1]; dp[0]=1; for(int i=1;i<=target;i++){ for(int n:nums){ if(i>=n){ dp[i]+=dp[i-n]; } } } return dp[target]; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/69798.html
摘要:前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写~现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。 顺序整理 1~50 1...
摘要:此时,若也正好减小为,说明当前集合是正解,加入数组。两个无法得到正解的情况是在为,而不为时,当然已经无法得到正解,。在不为而却已经小于等于的情况下,此时仍要加入其它数以令为,而要加入的数都是到的正整数,所以已无法满足令为的条件,。 Combination Sum I & II: link Combination Sum III Problem Find all possible com...
摘要:和唯一的不同是组合中不能存在重复的元素,因此,在递归时将初始位即可。 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...
摘要:参考思路和非常类似,只是这里需要增加进行重复处理的部分。题目要求题目中新添的要求包括数组中存在重复值,而且数组中每个值只可以使用一次。需要注意的是,既然数组中存在重复的值,就要注意可能会将重复的情况加入结果数组。 参考 思路和leetcode39 combination sum 非常类似,只是这里需要增加进行重复处理的部分。请参考我对leetcode39进行解答的这篇博客。 题目要求 ...
摘要:题目要求输入和,找到所有个不同数字的组合,这些组合中数字的和为参考,解答这是一道典型的的题目,通过递归的方式记录尝试的节点,如果成功则加入结果集,如果失败则返回上一个尝试的节点进行下一种尝试。 题目要求 Find all possible combinations of k numbers that add up to a number n, given that only numbe...
阅读 2104·2021-11-23 10:06
阅读 3456·2021-11-11 16:54
阅读 3336·2019-08-29 17:31
阅读 3563·2019-08-29 17:05
阅读 2165·2019-08-26 13:36
阅读 2154·2019-08-26 12:17
阅读 519·2019-08-26 12:12
阅读 1668·2019-08-26 10:19