C#LeetCode刷题之#40-组合总和 II（Combination Sum II）
问题
该文章已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3666 访问。
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
输入: candidates = [10,1,2,7,6,1,5],
target = 8,
所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
输入: candidates = [2,5,2,1,2],
target = 5,
所求解集为: [ [1,2,2], [5] ]
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates 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.
Input: candidates = [10,1,2,7,6,1,5],
target = 8,
A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
Input: candidates = [2,5,2,1,2],
target = 5,
A solution set is: [ [1,2,2], [5] ]
示例
该文章已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3666 访问。
public class Program {
public static void Main(string[] args) {
var candidates = new int[] { 10, 1, 2, 7, 6, 1, 5 };
var target = 8;
var res = CombinationSum2(candidates, target);
ShowArray(res);
Console.ReadKey();
}
private static void ShowArray(IList<IList<int>> candidates) {
foreach(var candi in candidates) {
foreach(var num in candi) {
Console.Write($"{num} ");
}
Console.WriteLine();
}
Console.WriteLine();
}
public static IList<IList<int>> CombinationSum2(int[] candidates, int target) {
var res = new List<IList<int>>();
if(candidates.Length == 1) {
if(candidates[0] == target) {
res.Add(candidates);
return res;
}
}
var candi = new List<int>();
Array.Sort(candidates);
Combination(candidates, -1, target, candi, ref res);
return res;
}
public static void Combination(int[] candidates,
int start,
int target,
List<int> candi,
ref List<IList<int>> res) {
if(target < 0) return;
if(target == 0) {
if(!res.Any(r => r.SequenceEqual(candi))) {
res.Add(candi);
}
return;
}
for(var i = start + 1; i < candidates.Length; i++) {
candi.Add(candidates[i]);
Combination(candidates, i, target - candidates[i], candi.ToList(), ref res);
candi.RemoveAt(candi.Count - 1);
while(i < candidates.Length - 1 && candidates[i] == candidates[i + 1]) i++;
}
}
}
以上给出1种算法实现，以下是这个案例的输出结果：
该文章已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3666 访问。
1 2 5
1 7
1 1 6
2 6
分析
显而易见， 以上算法的时间复杂度为：O(n2)O(n^2)O(n2) 。
最新文章
- 如何：在 SharePoint 中创建外部列表
- spring mvc基础配置
- 如何使用TestFlight进行Beta测试
- Unquotted string '＂2016-07-19＂'
- 转：视频压缩的基本概念(x264解压包)
- 1346. Intervals of Monotonicity（ｄｐ）
- LNMP笔记：更改网站文件和MySQL数据库的存放目录
- LeetCode初体验—twoSum
- SNA社交网络算法
- java中，Date数据类型和JSONObject数据类型之间的转换
- JS中判定问题
- MongoDB基础学习
- Docker使用Link与newwork在容器之间建立连接
- 脚本解决.NET MVC按钮重复提交问题
- java使用Iterator 迭代器
- python数据结构-如何让字典有序
- 配置MySQL GTID(Global Transaction IDs)复制
- MySQL数据库服务器整体规划(go)
- spring mvc 默认页面
- 利用ansible来做tomcat应用的持续交付