Java Algorithm для всех подмножеств массива (с целыми числами), удовлетворяющих сумме?

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}

Solution пишет мной не служит цели, Может кто-нибудь, пожалуйста, помогите здесь и указать, что не так в алгоритме или там любой другой лучший способ решения.

Заранее спасибо.

код ниже:

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