java - 在Java中如何获得数组中所有可能的不同和

Question

所有可能的不同和意味着数组中任何一个、两个、三个到 n（数组的长度）个数的和。例如，如果给定数组是 [2,2,3]，则数组中的一个数字的和就是数组本身 [2,2,3]，那么数组中任意两个数字的和就是 [4,5]数组中三个数之和为 [7] 因此，结果应该是所有可能的和的组合，即 [2,3,4,5,7] 只是算法的想法，不需要具体代码. 谢谢

Answer 1

最简单的方法是简单地迭代并获取总和并将它们添加到不允许重复的集合中。

Answer 2

要求的代码：

//following taken from http://rosettacode.org/wiki/Power_set#Java
public static <T extends Comparable<? super T>> LinkedList<LinkedList<T>> BinPowSet(
        LinkedList<T> A){
    LinkedList<LinkedList<T>> ans= new LinkedList<LinkedList<T>>();
    int ansSize = (int)Math.pow(2, A.size());
    for(Integer i= 0;i< ansSize;++i){
        String bin= Integer.toString(i, 2); //convert to binary
        while(bin.length() < A.size())bin = "0" + bin; //pad with 0's
        LinkedList<T> thisComb = new LinkedList<T>(); //place to put one combination
        for(int j= 0;j< A.size();++j){
            if(bin.charAt(j) == '1')thisComb.add(A.get(j));
        }
        Collections.sort(thisComb); //sort it for easy checking
        ans.add(thisComb); //put this set in the answer list
    }
    return ans;
}
//use would be
Set<Integer> sums = new HashSet<Integer>();
LinkedList<Integer> powerList = new LinkedList<Integer>(Arrays.<Integer>asList(arr));
for(Collection<Integer> sumEntry : BinPowSet(powerList)) {
    int x = 0;
    for(Integer y : sumEntry) {
        x += y;
    }
    sums.add(x);
}
return sums;

请注意，可以删除重复项。加法是可交集的，因此集合中不将单个元素添加两次的任何元素的总和，以任何顺序，都将出现在上面。

另请注意，虽然考虑了 Guava 的 Sets.powerSet()，但它需要一个实际的 Set 作为输入，这将不允许重复（示例中存在）。

Answer 3

我将按以下方式处理这个问题。首先，我将构建一个函数来计算组合。

组合（对象 [] A，int r）

这个函数将返回来自 A 的所有 nCr 组合，其中 n = A.length 一旦我有了这个函数，我可以为 r=1、2、3... 调用它并打印总和。

编写组合程序是一个非常标准的技术面试问题。

Answer 4

public class StackOverflow {
static Set<Integer> tree=new TreeSet<Integer>();
public static void main(String args[]) {
    int [] array= {2,2,3};
    getAllSums(array,0,0);
    tree.remove(0);
    for (Integer i: tree)
        System.out.println(i);


}
public static void getAllSums(int[] numbersArray, int starting, int sum)
{   
    if(numbersArray.length == starting)
    {      
        tree.add(sum);    
        return;
    }
    int value = sum + numbersArray[starting];
    getAllSums(numbersArray, starting + 1, value);
    getAllSums(numbersArray, starting + 1, sum); 
}