in 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; 

注意，複製可以被刪除。加法是共享的，因此，任何不以任何次序添加單個元素兩次的集合中的元素的總和將出現在上面。

另請注意，雖然考慮了番石榴的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); 
}