给定一个数t,以及n个数，在这n个数中找到加和为t的所有集合，例如t=4,n=6,这6个数为（4，3，2，2，1，1）这样输出就有4个不同的组合它们的加和为4: 4,3+1,2+2,and 2+1+1,请设计一个高效算法实现这个需求
------解决方案--------------------------------------------------------
先对 n 个数进行排序，然后找到 <= t 的数，然后做循环得出不同的组合
------解决方案--------------------------------------------------------
帮你顶下
------解决方案--------------------------------------------------------
------解决方案--------------------------------------------------------
帮顶~~~~~~~~~~~~~~~~~
------解决方案--------------------------------------------------------
如果不用输出的话其实是很简单的
可以建个链表 保存数组内元素的所有可能和
那样可以在O(logn)内完成
如果要输出其实也可以变下方式 一样不是很难
------解决方案--------------------------------------------------------
大概写了下，勉强能实现，但是效率不大高。给大家做个参考，欢迎改进
- Java code
import java.util.*;public class Test { public static void main(String[] args) { int number = 9; int[] array = { -9,-8,-7,-6,-5,-4,-3,-2,-1,1, 2, 3, 4, 5, 6, 7, 8, 9 }; List<String> list = f(number, array); for (String s : list) System.out.println(s); } static List<String> f(int number, int[] array) { List<String> list = new ArrayList<String>(); // 这里先排除掉数组中与要找的数字相同的数，否则后面递归里面一直都在第一个循环中返回。这里不太好 for (int i = 0; i < array.length; i++) if(array[i] == number){ list.add(number + ""); array[i] = 0; } for (int i = 0; i < array.length; i++) { if (array[i] == number) { list.add(number + ""); continue; } String s = g(i, number, array); if (!s.endsWith("null")) list.add(s); } return list; } static String g(int startIndex, int number, int[] array) { for (int i = startIndex; i < array.length; i++){ if(array[i] == 0) continue; if (array[i] == number) return array[i] + ""; } for (int i = startIndex; i < array.length; i++) if (array[i] < number) { number -= array[i]; return array[i] + " + " + g(i + 1, number, array); } return null; }}
------解决方案--------------------------------------------------------
package cn.gao.util.algorithm;
import java.util.ArrayList;
import java.util.Collection;
@SuppressWarnings("serial")
public class BagList extends ArrayList {
@SuppressWarnings("unchecked")
public BagList(int num)
{
super.add(num);
}
@SuppressWarnings("unchecked")
public BagList(Collection<Integer> collection,int num)
{
for(Integer o:collection)
{
this.add(o);
}
this.add(num);
}
@Override
public boolean equals(Object arg0) {
// TODO Auto-generated method stub
if(arg0==this)
{
return true;
}
if(arg0==null&&this!=null||this==null&&arg0!=null)
{
return false;
}
if(arg0.getClass()!=BagList.class)
{
return false;
}
else{
BagList b=(BagList)arg0;
if(this.size()!=b.size())
{
return false;
}
for(Object o:b)
{
if(!this.contains(o))
{
return false;
}
}
return true;
}
}
@Override
public int hashCode() {
int sum=0;
for(Object o:this)
{
sum+=(Integer)o;
}