アルゴリズム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));

        }

               ,          ,        ,       。