適用於數組的所有子集（具有整數）的Java算法滿足總和？

Question

我正在研究Java程序，它給出了所有可能的數組的數量，這些數字有助於給定的總和。

例如對於總和we have an Array of numbers {1,2,2,3,4,5} these might be unsorted

可能的子集/輸出「5」：{1,2,2} {3,2} {4,1} & {5}

解決方案寫的我不頂用，可有一個人請幫助這裏指出什麼是錯的算法還是有任何其他更好的解決方法。

在此先感謝。

下面的代碼：

public static List<List<Integer>> possibleCombinations(int[] array, 
    int requiredSum) { 
Arrays.sort(array); 
List<List<Integer>> result = new ArrayList<List<Integer>>(); 
HashSet<String> hello = new HashSet<String>(); 
for (int i = 0; i < array.length; i++) { 
    if (array[i] > requiredSum) { 
     break; 
    } else if (array[i] == requiredSum) { 
     List<Integer> single = new ArrayList<Integer>(); 
     single.add(requiredSum); 
     result.add(single); 
     return result; 
    } 
    for (int j = i + 1; j < array.length; j++) { 
     if (array[j] > requiredSum) { 
      break; 
     } else if (array[j] == requiredSum) { 
      List<Integer> single = new ArrayList<Integer>(); 
      single.add(requiredSum); 
      result.add(single); 
      return result; 
     } 
     List<Integer> possibility = new ArrayList<Integer>(); 
     possibility.add(array[i]); 
     int sum = 0; 
     sum += array[i]; 
     for (int k = j; k < array.length; k++) { 
      if ((sum + array[k]) < requiredSum) { 
       possibility.add(array[k]); 
       sum += array[k]; 
      } else if (sum + array[k] == requiredSum) { 
       possibility.add(array[k]); 
       result.add(possibility); 
       break; 
      } else { 
       if(possibility.isEmpty() || possibility.size()==1){ 
        break; 
       } 
       sum -= possibility.get(possibility.size() - 1); 
       possibility.remove(possibility.size() - 1); 
       k--; 
       continue; 
      } 
     } 

    } 
} 

return result; 

}

Answer 1

我希望它可以幫助你。 我沒有編譯代碼，但我很確定它會起作用。

它適用於複雜度O（2^N），其中N是元素的數量。

void printSubsetSum(int []nums,int targetSum) { 
    int n = nums.length; 

    // generate all possible combination from binary representation 
    for(int mask=(1<<n)-1;mask>0;mask--) { 
     List<Integer> list = new ArrayList<Integer>(); 

     // check by bit operation 
     for(int i=0;i<n;i++) { 
      // if ith bit is on then we add our candidate number 
      if((mask & (1<<i))!=0) list.add(nums[i]); 
     } 

     // sum all element in list 
     int sum = 0; 
     for(int x:list) sum += x; 

     // if the sum equals targetSum then we print our list 
     if(sum==targetSum) System.out.println(list); 
    } 
} 

我的解決方案是如何工作

假設我們有測試輸入{1,2,2,3,4,5}

有6個號碼，我們要找到每一個對於總和組合= 5

我的解決方案的工作原理是產生由式（2^6 - 1）的二進制數，直到1.

63 = 111111 
62 = 111110 
61 = 111101 
.. 
3 = 000011 
2 = 000010 
1 = 000001 

對於每個1位的二進制數，我從testinput中選取值並對其進行求和。

例子：

101101 from {1,2,2,3,4,5} that means 1 + 2 + 3 + 5. 
000101 from {1,2,2,3,4,5} that means 3 + 5. 

Answer 2

我已經寫了下面的算法，但在所有情況下不起作用，只打印子集的後續安排。

public static List<List<Integer>> possibleCombinations(int[] array, 
     int requiredSum) { 
    Arrays.sort(array); 
    List<List<Integer>> result = new ArrayList<List<Integer>>(); 
    HashSet<String> hello = new HashSet<String>(); 
    for (int i = 0; i < array.length; i++) { 
     if (array[i] > requiredSum) { 
      break; 
     } else if (array[i] == requiredSum) { 
      List<Integer> single = new ArrayList<Integer>(); 
      single.add(requiredSum); 
      result.add(single); 
      return result; 
     } 
     for (int j = i + 1; j < array.length; j++) { 
      if (array[j] > requiredSum) { 
       break; 
      } else if (array[j] == requiredSum) { 
       List<Integer> single = new ArrayList<Integer>(); 
       single.add(requiredSum); 
       result.add(single); 
       return result; 
      } 
      List<Integer> possibility = new ArrayList<Integer>(); 
      possibility.add(array[i]); 
      int sum = 0; 
      sum += array[i]; 
      for (int k = j; k < array.length; k++) { 
       if ((sum + array[k]) < requiredSum) { 
        possibility.add(array[k]); 
        sum += array[k]; 
       } else if (sum + array[k] == requiredSum) { 
        possibility.add(array[k]); 
        result.add(possibility); 
        break; 
       } else { 
        if(possibility.isEmpty() || possibility.size()==1){ 
         break; 
        } 
        sum -= possibility.get(possibility.size() - 1); 
        possibility.remove(possibility.size() - 1); 
        k--; 
        continue; 
       } 
      } 

     } 
    } 

    return result; 
}