這個程序應該是遞歸的，給我的整數

Question

數組的所有可能的資金，但我正在複製的答案時，我的數組大小超過2

public ArrayList sum(int[]array, int arrayIndex, int newArrayIndex){ 

    if (arrayIndex<array.length){ 
     if (newArrayIndex<pow(2,arrayIndex)){ 
     if(newarray.isEmpty()){ 
      newarray.add(0); 
     } 
     newarray.add(newarray.get(newArrayIndex)+array[arrayIndex]); 
     sum(array,arrayIndex,newArrayIndex+1); 
     sum(array,arrayIndex+1,newArrayIndex-newArrayIndex); 
     } 
    } 
    return newarray; 

}

例如

public static void main(String[] args) { 
    int[] numarray ={1,2,3}; 
    NumbersAddition num = new NumbersAddition(numarray); 
    num.sum(numarray,0,0); 
} 

output: [0, 1, 2, 3, 3, 4, 5, 6, 3, 4, 5, 6] 
Should be: 0,1,2,3,3,4,5,6 

有人可以告訴我什麼是錯的代碼？

Answer 1

對於添加的每個元素，您正在進行到下一個arrayIndex一次。

你應該每做一遍，每次你瀏覽整個新陣列。

下面是用，使得它的獨立和工作，你所希望的方式所需要的最小的改動你的程序：

import java.util.*; 
import static java.lang.Math.pow; 

class NumbersAddition { 
    ArrayList<Integer> newarray = new ArrayList<Integer>(); 
    NumbersAddition(Object unnecessary) {} 

    public ArrayList sum(int[]array, int arrayIndex, int newArrayIndex){ 
    if (arrayIndex<array.length){ 
     if (newArrayIndex<pow(2,arrayIndex)){ 
     if(newarray.isEmpty()){ 
      newarray.add(0); 
     } 
     newarray.add(newarray.get(newArrayIndex)+array[arrayIndex]); 
     sum(array,arrayIndex,newArrayIndex+1); 
     } else { 
     // Just do this when newArrayIndex has reached the end: 
     sum(array,arrayIndex+1,newArrayIndex-newArrayIndex); 
     } 
    } 
    return newarray; 
    } 

    public static void main(String[] args) { 
    int[] numarray ={1,2,3}; 
    NumbersAddition num = new NumbersAddition(numarray); 
    num.sum(numarray,0,0); 
    System.out.println(num.newarray); 
    } 
} 

順便說一句，這個代碼是兩個嵌套的for循環一尾遞歸改寫。

更規範的遞歸解決方案是根據sums(array, length-1)定義sums(array, length)，sums(array, 0) = {0}作爲您的基本情況。

Answer 2

您的第二個sum應該只發生如果你的第二個條件（newArrayIndex < pow(2, arrayIndex)）不滿足。

提示：

• ，而不是總檢查，如果您的列表是空的，只是在初始化加0。
• 您事先知道新陣列所需的大小。您可以創建一個長度爲Math.pow(2, array.length)的數組，並在位置pow(2, arrayIndex) + newArrayIndex中添加您的元素，而不是列表。這反覆勝過呼叫add。

編輯：我做了使用數組並隱藏初始化明細的附加方法的實現：

private static void sumAux(int[] array, int i, int[] powerSet, int j) 
{ 
    if (i < array.length) 
    { 
     int pow = (int) Math.pow(2, i); 
     if(j < pow) 
     { 
      powerSet[pow + j] = powerSet[j] + array[i]; 
      sumAux(array, i, powerSet, j + 1); 
     } 
     else 
     { 
      sumAux(array, i + 1, powerSet, 0); 
     } 
    } 
} 

public static int[] sum(int[] array) 
{ 
    int[] powerSet = new int[(int)Math.pow(2, array.length)]; 
    sumAux(array, 0, powerSet, 0); 
    return powerSet; 
} 

public static void main(String[] args) 
{ 
    int[] array = {2, 3, 7, 13}; 
    int[] powerSet = sum(array); 
    for (int i : powerSet) 
    { 
     System.out.print(i + " "); 
    } 
}