java - Javaで配列内のすべての可能な個別の合計を取得する方法

Question

可能な個別の合計はすべて、配列内の任意の 1、2、3 から n (配列の長さ) までの合計を意味します。たとえば、指定された配列が [2,2,3] の場合、配列内の 1 つの数値の合計は配列自体 [2,2,3] であり、配列内の任意の 2 つの数値の合計は [4,5] です。配列内の 3 つの数値の合計は [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;

重複は削除できることに注意してください。足し算は共有的であるため、単一の要素を 2 回追加しないセットの要素の合計は、任意の順序で取られ、上記に存在します。

また、Guava の Sets.powerSet() が考慮されましたが、入力として実際の Set が必要であり、重複が許可されないことに注意してください (例に存在していました)。

Answer 3

私は次のように質問に取り組みます。まず、組み合わせを計算する関数を作成します。

組み合わせ（オブジェクト[] A、int r）

この関数は、A からすべての nCr の組み合わせを返します。ここで、n = A.length この関数を配置したら、r=1、2、3... に対して呼び出して、合計を出力できます。

コンビネーション ルーチンを書くことは、かなり標準的な技術面接の質問です。