一个数据组合算法的问题，求教论坛里各位高人
目前需求是这样的： 我们有一个int型的既定的数M ，然后服务器给了很多数据，经过处理之后都是int型的数据，我们称之为数据N（数据个数随着请求的变化而变化），现在要做的就是，如何使用N中的数据进行组合（加法运算，可能是两数相加、可能是三数相加。当然也有可能直接就是M==N），使得组合的数据经过相加之后得到M的值。比如说，我想得到6 ，但是服务器给我了 1 ，2,3,4，6 那么我得到的组合应该就是
6
2 4
3 3
1 1 4
1 2 3
四个数相加的情况暂不考虑。
求教论坛的各位大神我该如何设计？本人算法方面不行，自己摸索着用 其中一个元素跟其他的元素进行相加的方法，测试发现第一效率低下，第二没有完全生成我想要的组合。因为这种方法有两方面的问题，如果服务器给我的数据只有一条我需要单独进行处理，第二不能正确生成三数相加的组合。。。。。。求教各位大师。 java组合算法 算法
[解决办法]
import java.util.*;
import static java.lang.System.out;
public class Test24
{
static ArrayList<Integer> getAdd1Type(final int M ,final ArrayList<Integer> Ns)
{
int size = Ns.size();
int index = size/2;
ArrayList<Integer> returnList = new ArrayList<Integer>();
//这种情况，就要求前部遍历，因为无法定位
if (Ns.get(index) == M)
{
for (int i =0; i<size;i++ )
{
if (Ns.get(i) == M)
{
returnList.add(Ns.get(i));
}
}
return returnList;
}
if (Ns.get(index) > M)
{
//0~index-1
for (int i = 0; i< index; i++ )
{
if (Ns.get(i) == M)
{
returnList.add(Ns.get(i));
}
}
return returnList;
}
else
{
//index+1~size
for (int i = index+1; i< size; i++ )
{
if (Ns.get(i) == M)
{
returnList.add(Ns.get(i));
}
}
return returnList;
}
}
static ArrayList<String> getAdd2Type(final int M ,final ArrayList<Integer> Ns)
{
ArrayList<String> listReturn = new ArrayList<String>();
//这里应该可以选择反向遍历的方式进行比较
int count = Ns.size();
for (int i = 0; i<count ;i++ )
{
if (Ns.get(i)>=M)
{
continue;
}
for (int j = i+1; j<count ;j++ )
{
if (Ns.get(j)>=M)
{
continue;
}
if ((Ns.get(i) +Ns.get(j))==M )
{
listReturn.add("{"+Ns.get(i)+","+Ns.get(j)+"}");
}
}
}
return listReturn;
}
static ArrayList<String> getAdd3Type(final int M ,final ArrayList<Integer> Ns)
{
ArrayList<String> listReturn = new ArrayList<String>();
//这里应该可以选择反向遍历的方式进行比较
int count = Ns.size();
for (int i = 0; i<count ;i++ )
{
if (Ns.get(i)>=M)
{
continue;
}
for (int j = i+1; j<count ;j++ )
{
if (Ns.get(j)>=M)
{
continue;
}
for (int k=j+1;k<count ;k++ )
{
if ((Ns.get(i) +Ns.get(j)+Ns.get(k))==M )
{
listReturn.add("{"+Ns.get(i)+","+Ns.get(j)+","+Ns.get(k)+"}");
}
}
}
}
return listReturn;
}
public static void main(String[] args)
{
int M = 20;
ArrayList<Integer> Ns = new ArrayList<Integer>();
//准备测试数据
Random rs =new Random( );
for (int i = 1; i <= 24 ;i++ )
{
Ns.add(rs.nextInt(50));
}
out.println("服务器给的数字");
out.println(Ns);
//为了节约CPU时间，先对ArrayList进行排序，有顺序的数容易计算
Collections.sort(Ns);
//计算排列组合的数目
//1个数的时候
out.println("1个数的时候找到");
out.println(getAdd1Type(M,Ns));
out.println("2个数的时候找到");
out.println(getAdd2Type(M,Ns));
out.println("3个数的时候找到");
out.println(getAdd3Type(M,Ns));
System.out.println("Hello World!");
}
}
import java.util.LinkedList;
import java.util.List;
public class Hello {
public static void foo(int[] elements,
int currentIndex,
int currentSum,
final int resultSum,
List<Integer> results) {
if (currentSum > resultSum) {
return;
}
if (currentSum == resultSum) {
System.out.println(results);
return;
}
for (int i = currentIndex; i < elements.length; ++i) {
results.add(elements[i]);
foo(elements, i, currentSum + elements[i], resultSum, results); // 深度遍历
results.remove(results.size() - 1);
}
}
public static void main(String[] args) {
int[] elements = {1, 2, 3, 4, 5};
int resultSum = 6;
List<Integer> results = new LinkedList<Integer>();
foo(elements, 0, 0, resultSum, results);
}
}
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 2]
[1, 1, 1, 3]
[1, 1, 2, 2]
[1, 1, 4]
[1, 2, 3]
[1, 5]
[2, 2, 2]
[2, 4]
[3, 3]
