LeetCode(中等)组合总和 II(c#)
程序员文章站
2022-07-07 20:41:25
题目为 给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。说明:所有数字(包括目标数)都是正整数。解集不能包含重复的组合。与组合总数逻辑差不多,不过递归时,不能给for的开始位数传当前的i了,要加一,然后加个键值对去判断是否存在重复。代码如下IList> res = new List
题目为 给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明:
所有数字(包括目标数)都是正整数。
解集不能包含重复的组合。
与组合总数逻辑差不多,不过递归时,不能给for的开始位数传当前的i了,要加一,然后加个键值对去判断是否存在重复。代码如下
IList<IList<int>> res = new List<IList<int>>();
Dictionary<string, int> dic = new Dictionary<string, int>();
public IList<IList<int>> CombinationSum2(int[] candidates, int target)
{
Array.Sort(candidates);
GetAllCom(candidates, target, 0, new List<int>(), 0);
return res;
}
public void GetAllCom(int[] candidates, int target, int sum, List<int> temp, int begin)
{
if (sum == target)
{
StringBuilder sb = new StringBuilder();
foreach (var item in temp)
{
sb.Append(item);
}
if (!dic.ContainsKey(sb.ToString()))
{
res.Add(new List<int>(temp));
dic.Add(sb.ToString(), 1);
}
return;
}
for (int i = begin; i < candidates.Length; i++)
{
if (sum + candidates[i] > target)
{
return;
}
temp.Add(candidates[i]);
GetAllCom(candidates, target, sum + candidates[i], temp, i+1);
temp.RemoveAt(temp.Count() - 1);
}
}
本文地址:https://blog.csdn.net/weixin_34024244/article/details/107382964
推荐阅读
-
#leetcode刷题之路40-组合总和 II
-
【刷题1】LeetCode 39. 组合总和 java基础
-
动态规划中等 leetcode213. 打家劫舍 II
-
分治算法中等 leetcode240. 搜索二维矩阵 II
-
LeetCode(中等)组合总和 II(c#)
-
解题思路-LeetCode第39题:组合总和
-
回溯-LeetCode39. 组合总和
-
【LeetCode】39. 组合总和 & 40. 组合总数 II & 1~n 这n个数组合成 m
-
LeetCode数据库中等题:1205. 每月交易II
-
Leetcode之回溯法专题-40. 组合总和 II(Combination Sum II)