想法是利用递归的方式来解决。每次都从序列中循环出一个数与特定值做比较，三种情况：
① 等于 --- 存进结果数组
② 小于 --- 扔进递归，特定值为父递归的特定值减去此次循环出的值
③ 大于 --- 抛弃
在循环完成之后返回值之前给结果集去重。
之后判断剩下的结果集的自身的数相加是否都等于特定值，抛弃不等于者。
返回。
用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;
}
}
}
网友评论