题目为 给定一个数组 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
黄山市民网:https://www.huangshanshimin.com/