日期:2014-05-20  浏览次数:20781 次

求一个算法。。
比方说一个数组中有10个数据1,2,3,4,5,6,7,8,9,10
我想要一个算法可以算出任意多的数据的和为12的情况
比方说
1+2+3+6=12
2+10=12
就是要得出所有这些数据加起来能够等于12的情况
是否能做到呢

------解决方案--------------------
一下是完整代码,采用穷举法,递归实现:

import java.util.ArrayList;
import java.util.Arrays;

public class Main {

/**
* @param args
*/
public static void main(String[] args) {

int[] a = {4, 5, 9, 8, 6, 2, 7, 3, 1, 10};
final int SUM = 20;
ArrayList <String> result = findExp(a, SUM);
for(String s:result) {
System.out.println(s);
}
}


private static ArrayList <String> findExp(int[] a, final int SUM) {
ArrayList <String> result = new ArrayList <String> ();
Arrays.sort(a);
ArrayList <Integer> l = new ArrayList <Integer> ();
find(a, SUM, 0, l, result);
return result;
}

private static void find(int[] a, final int SUM, int cur, ArrayList <Integer> l, ArrayList <String> result) {
int beg = l.size() == 0 ? 0 : l.get(l.size()-1)+1;
for(int i=beg; i <a.length; i++) {
cur += a[i];
if(cur <SUM) {
l.add(i);
find(a, SUM, cur, l, result);
cur -= a[i];
l.remove(l.size()-1);
}else if(cur == SUM) {
StringBuilder s = new StringBuilder();
for(int x:l) {
s.append(a[x]);
s.append( " + ");
}
s.append(a[i]);
s.append( " = ");
s.append(SUM);
result.add(s.toString());

break;
}else {
break;
}
}
}
}