算法：求序列中和为特定值的集合

想法是利用递归的方式来解决。每次都从序列中循环出一个数与特定值做比较，三种情况：

        ①    等于    ---    存进结果数组

        ②    小于    ---    扔进递归，特定值为父递归的特定值减去此次循环出的值

        ③    大于    ---    抛弃

在循环完成之后返回值之前给结果集去重。

之后判断剩下的结果集的自身的数相加是否都等于特定值，抛弃不等于者。

返回。

用C#实现的效果：

image.png

接下来是用C#实现的代码:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Threading;

namespace test
{
    class Program
    {
        const int COUNT = 10;

        const int MIDDLE = -1;

        static int[] iArray;
        static void Main(string[] args)
        {
            //  随机生成序列
            Random random = new Random(DateTime.Now.Millisecond);
            iArray = new int[COUNT];
            for (int i = 0; i < COUNT; i++)
            {
                iArray[i] = random.Next(1, 10);
            }
            foreach (var i in iArray)
            {
                Console.Write(i + " ");
            }
            Console.WriteLine();

            //  指定一个特定数，并且找出序列中和为特定数的组合
            int s = 12;
            Console.WriteLine("特定值为：" + s);
            var r = Poling(s);
            foreach (var i in r)
            {
                if(i!=MIDDLE)
                Console.Write(" 第"+i+"号："+iArray[i]);
                else
                    Console.WriteLine();
            }

            Console.ReadLine();
        }

        /// <summary>
        /// 递归-求出指定数在序列中和的组合
        /// </summary>
        /// <param name="x">指定数</param>
        /// <returns>组合集</returns>
        static List<int> Poling(int x)
        {
            //  轮查可以形成或等于指定数x的数集
            var _array = new List<int>();
            var result = new List<int>();
            for (int i = 0; i < iArray.Length; i++)
            {
                if (iArray[i] == x)     //可以形成
                {
                    result.Add(i);
                    result.Add(MIDDLE);
                }
                else if (iArray[i] < x)     //小于指定数，还需要继续寻找能够组成差值的数集
                {
                    var temp = Poling(x - iArray[i]);   //递归调用此方法
                    temp = Regroup(i, temp);    
                    result.AddRange(temp);
                }
            }

            //  去重
            result = RemoveRepeat(result);  

            //  把和不等于指定数x的数集删除
            int add = 0;
            List<int> _result = new List<int>();
            List<int> t = new List<int>();
            for (int i = 0; i < result.Count; i++)
            {
                if (result[i] == MIDDLE)
                {
                    if (add == x)
                    {
                        _result.AddRange(t);
                        _result.Add(MIDDLE);
                        t = new List<int>();
                        add = 0;
                    }
                }
                else
                {
                    t.Add(result[i]);
                    add += iArray[result[i]];
                }
            }

            //  返回值-返回值为iArray的序号（不为值）
            //  如 0，3，6，9，-1
            //  其中-1 为MIDDLE常量
            return _result;
        }


        /// <summary>
        /// 去重方法
        /// </summary>
        /// <param name="list">需要去重的数据</param>
        /// <returns></returns>
        static List<int> RemoveRepeat(List<int> list)
        {
            List<List<int>> cut = new List<List<int>>();
            List<int> temp = new List<int>();
            foreach (var i in list)
            {
                if (i == MIDDLE)
                {
                    cut.Add(temp);
                    temp = new List<int>();
                }
                else
                {
                    temp.Add(i);
                }
            }


            //  单列去重
            for (int i = 0; i < cut.Count; i++)
            {
                cut[i] = RemoveSignRepeat(cut[i]);
            }

            //  多列去重
            int count = cut.Count;
            for (int i = 0; i < count - 1; i++)
            {
                for (int j = i + 1; j < count; j++)
                {
                    if (IsRepeat(cut[i], cut[j]))
                    {
                        cut.Remove(cut[j]);
                        count--;
                    }
                }
            }

            var result = new List<int>();
            foreach (var i in cut)
            {
                foreach (var j in i)
                {
                    result.Add(j);
                }
                result.Add(MIDDLE);
            }
            return result;
        }

        /// <summary>
        /// 重组
        /// </summary>
        /// <param name="y"></param>
        /// <param name="list"></param>
        /// <returns></returns>
        static List<int> Regroup(int y ,List<int> list)
        {
            var _list = new List<int>();
            for (int i = 0;i<list.Count;i++)
            {
                if (i == 0 || list[i] == MIDDLE)
                {
                    _list.Add(y);
                }
                _list.Add(list[i]);
            }
            return _list;
        }


        /// <summary>
        /// 判断两个序列是否相同
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        static bool IsRepeat(List<int> a ,List<int> b){
            int count =a.Count;
            int c=0;
            if(count ==b.Count){
                foreach (var i in a)
                {
                    foreach (var j in b)
                    {
                        if (i == j)
                            c++;
                    }
                }
            }
            if (c > count)
            {
                return true;
            }
            if (c == count)
                return true;
            else
                return false;
        }

        /// <summary>
        /// 单列去重
        /// </summary>
        /// <param name="a"></param>
        /// <returns></returns>
        static List<int> RemoveSignRepeat(List<int> a)
        {
            List<int> result = new List<int>();
            for (int i = 0; i < a.Count; i++)
            {
                if (!result.Contains(a[i]))
                {
                    result.Add(a[i]);
                }
            }
            return result;
        }
    }
}