一道阿里巴巴算法笔试题

给定一个数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 的数，然后做循环得出不同的组合
[解决办法]
帮你顶下

[解决办法]

探讨

先对 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;
} 
 
return sum;
}
}




package cn.gao.util.algorithm;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;
/*
  * 0-1背包问题，已知给定一个数组，里面存放N个数的重量，然后你自己选出所有的重量等于M的组合情况
  */
public class ZeroOneBagTest {
private Map<Integer, Set<BagList>> bagMap=new HashMap<Integer, Set<BagList>>();//保存排列组合信息
private Set<BagList> newBagSet=new HashSet<BagList>();//临时Set，用于构建上面的Map
private int count=1;
private int[] a;
private int target;
public ZeroOneBagTest(int[] a,int target)
{
this.a=a;
this.target=target;
}
public void printZuHe()
{
ArrayList<BagList> newBagList=new ArrayList<BagList>();
f();
Set<Entry<Integer, Set<BagList>>> s=bagMap.entrySet();
for(Entry<Integer, Set<BagList>> ss:s)
{
System.out.println(ss.getKey()+"个数的组合有：");
for(BagList bg:ss.getValue())
{
System.out.println(bg);
if(sum(bg)==target)
{
newBagList.add(bg);
}
}
}
System.out.println("和值等于"+target+"组合一共有"+newBagList.size()+"种！");
for(BagList bs:newBagList)
{
System.out.println(bs);
}
}
public int sum(BagList bb)
{
int sum=0;
   for(Object o:bb)
   {  
   sum+=(Integer)o;
   }
   return sum;
}
public void f()
{
while(true)
{
if(count==1)
{
for(int k:a)
{
newBagSet.add(new BagList(k));
bagMap.put(1, newBagSet);
}
count++;
}
if(count==a.length+1)
{
break;
}
g();
bagMap.put(count, newBagSet);
count++;
}
}
public void g()
{
Set<BagList> newBagSet1=new HashSet<BagList>();
for(int k:a)
{
for(BagList bg:newBagSet)
{
if(!bg.contains(k))
{
newBagSet1.add(new BagList(bg,k));
}
}
}
newBagSet=newBagSet1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]={4,3,2,2,1,1};
long x=System.currentTimeMillis();
ZeroOneBagTest zz=new ZeroOneBagTest(a,4);
zz.printZuHe();
System.out.println(System.currentTimeMillis()-x);
}
}

写了一个实现算法，（自己实现了一个特殊的LIST）,不过中间用了大量的内存，不过索性的是执行的时间还算比较快。

[解决办法]
汗，一大早上来解题。

这是0-1背包的变形，如果按0-1背包处理会出现打印相同组合多次的情况，比如1重复了2次，那么，可能1+3打印出两次。为了消除这个重复，可一开始计算出重复次数，在规划的时候，依次看加入当前元素1，2，3，。。M次的子问题。

令result[v][i]表示，前1,2,..i个元素可构成和等于v的可能数。
那么result[v][i]的可能方案中可能包含a[i],也可能不包含，不包含的总数有result[v][i-1].
包含的情况有多种，可能包含一次，也可能包含2，3，。。n次。另外还可能只包含该元素，这时方案数要加1.
Assembly code
result[v][i]=∑(result[v-a[i]*k][i-1])+result[v][i-1]+((v%a[i])==0?1:0)
[解决办法]
回溯法
Java code
import java.util.LinkedList;public class SetSum {    int[] a;    int t;        SetSum(int[] a, int t) { this.a = a; this.t = t; }        void huisu(LinkedList<Integer> list, int i) {        int sum = 0;        for(Integer x : list) sum += x;        if(sum >= t) {            if(sum==t) System.out.println(list);            return;        }        for(int j=i; j<a.length; j++) {            list.add(a[j]);            huisu(list, j+1);            list.removeLast();        }    }        public static void main(String[] args) {        SetSum s = new SetSum(new int[]{1,1,2,2,3,4}, 4);        LinkedList<Integer> list = new LinkedList<Integer>();        s.huisu(list, 0);    }}