アルゴリズム1枚
2471 ワード
/// <summary>
/// Find all sub number groups that sum equal to a given number
/// </summary>
/// <param name="list">sorted list</param>
/// <param name="total">total number</param>
/// <returns>all sub number groups</returns>
private static IEnumerable<List<int>> FindCombination(List<int> list, int total)
{
var found = new List<List<int>>();
//[2,3,4] total:1
if (list.First() > total)
return found;
//[2] total:1
if (list.Count == 1 && list.First() != total)
return found;
//[1,2, 6] => [1,2]
if (list.Contains(total))
{
found.Add(new List<int> { total });
list.Remove(total);
}
//[1,2,3] => 1+2+3 =6
if (list.Sum() == total)
{
found.Add(list);
return found;
}
//travel every item to find combination
for (var i = 0; i < list.Count; i++)
{
var seed = list[i];
var subTotal = total - seed;
var clonedList = new List<int>(list);
clonedList.RemoveAt(i);
var combinations = FindCombination(clonedList, subTotal);
foreach (var item in combinations)
{
item.Add(seed);
item.Sort();
if (!IsContainArray(found, item))
found.Add(item);
}
}
return found;
}
/// <summary>
/// To check if an list of list contains a list
/// </summary>
/// <param name="list"></param>
/// <param name="item"></param>
/// <returns>contains or not</returns>
private static bool IsContainArray(IEnumerable<List<int>> list, IEnumerable<int> item)
{
return list.Select(l => string.Join(",", l)).Contains(string.Join(",", item));
}
, , , 。