Найти подмножество элементов в массиве, которое при суммировании равно любому другому элементу в массиве

Question

Я хотел бы написать алгоритм в Javascript для следующей проблемы.

Учитывая следующий массив [1,2,3,4,6], укажите количество подмножеств, равное любому другому элементу в массиве.

Например:

1+2 = 3 
1+3 = 4 
2+4 = 6 
1+2+3 = 6 

Ответ: 4 подмножества

можно вычислить сумму пар чисел, которые равны любой другой элемент в массиве; однако я не могу найти сумму из двух или более элементов (1 + 2 + 3), которые равны любому другому элементу массива.

Как бы я написал алгоритм для этого? Благодаря!

Answer 1

Вот очень простое решение, которое должно быть легко понято. Обратите внимание, что это не очень быстрый алгоритм, но для более коротких массивов он работает хорошо.

Идея заключается в том, чтобы генерировать битовую маску для каждой комбинации, а затем для каждой маски добавить номера в массиве, обозначенный 1 в битовой маске строке:

console.log("Number of subsets: " + getNumberOfSubsets([1, 2, 3, 4, 6], 2)); 

function getNumberOfSubsets(numbers, minimumNumbersInSubset) { 
    var numberOfBits = Math.pow(2, numbers.length); 
    var numOfSubsets = 0; 

    for (var i=0;i<numberOfBits;i++) { 
     var bitField = i.toString(2); 
     while(bitField.length < numbers.length) { 
      bitField = "0" + bitField; 
     } 

     var sum = 0; 
     var addedNumbers = []; 
     for (j=0;j<bitField.length;j++) { 
      if (bitField.charAt(j) == "1") { 
       sum += numbers[j]; 
       addedNumbers.push(numbers[j]); 
      } 
     } 

     if (addedNumbers.length >= minimumNumbersInSubset && numbers.indexOf(sum) !== -1) { 
      numOfSubsets += 1; 
      console.log("Iteration " + i + ": " + 
         bitField+", " + (addedNumbers.join("+") + "=" + sum)); 
     } 
    } 

    return numOfSubsets; 
} 

Выдает следующее в консоли показать успешные комбинации:

Iteration 10: 01010, 2+4=6 
Iteration 20: 10100, 1+3=4 
Iteration 24: 11000, 1+2=3 
Iteration 28: 11100, 1+2+3=6 
Number of subsets: 4 

Вот jsfiddle: http://jsfiddle.net/9HhSs/