проверку на наличие возможной комбинации значений в массиве, сумма которых равна заданному значению

Question

ДЛЯ ВЕДУЩИЙ:

Вопрос, для которого это предполагается дубликат, не затрагивает ряд вопросов.

1. Этот вопрос не о том, как операторы работают сами по себе, но как они функционируют в алгоритме, то почему эти операторы в этой точке.
2. Этот вопрос также включает в себя побитное сравнение '&' оператор, который
   другой вопрос не адресуется вообще.
3. Центральное понимание к ответу при условии, что путем присвоения
   combinationsCount = 1 << listSize один превращает итератора «I» в петле в векторе битов, которые могут быть испытаны в отношении конкретного «J», чтобы определить, , если оно должно быть включенных в сумму для тестирования.

Это решение проблемы изменения монет, я думаю. Код работает, насколько мне известно, но я не понимаю, как последний, если проверка:

if (i & (1 << j)) { 
    combinationSum += arr[j]; 
} 

работы в этом алгоритме (см. Ниже) Я столкнулся с этим, работая над учебником. Я бы очень признателен за любое объяснение того, как работает эта часть кода.

UPDATE:

Чтобы быть ясно, я понять ЧТО операторы делают, то есть немного сдвигая и побитовое сложение. Я хочу знать, как они работают в рамках алгоритма.

possibleCombinationSumN(arr, n) { 
    if (arr.indexOf(n) >= 0) { 
    return true; 
    } 

    if (arr[0] > n) { 
    return false; 
    } 

    if (arr[arr.length - 1] > n) { 
    arr.pop(); 
    return possibleCombinationSumN(arr, n); 
    } 

    var listSize = arr.length, combinationsCount = (1 << listSize) 
    for (var i = 1; i < combinationsCount; i++) { 
    var combinationSum = 0; 
    for (var j = 0; j < listSize; j++) { 
     if (i & (1 << j)) { 
     combinationSum += arr[j]; 
     } 
    } 
    if (n === combinationSum) { 
     return true; 
    } 
    } 
    return false; 
}; 

Answer 1

i служит bitvector (строка нулей и единиц), что включать или выключать при участии соответствующих значений массива в сумме.

Например, если arr имеет 4 элемента, когда i - 11, его двоичное представление - 0b1011; это означает, что мы должны подвести итог arr[3] + arr[1] + arr[0] и оставить arr[2].

Теперь - для четырехэлементного массива i будет идти от 0 до 15. Зачем? Потому что 1 << arr.length является двоичным 0b10000 (0b1 сместился влево на четыре позиции), или 16, и мы зацикливаемся под ним. Это дает нам двоичные значения между 0b0000 и 0b1111 - т. Е. Все возможные комбинации из четырех и нулей. Если мы затем суммируем соответствующие значения массива, мы проверим все возможные комбинации сумм.

i & (1 << j) испытания, если j-й бит 1.

Say j является 3 и i вышеупомянутая 11 (0b1011).1 << j - 0b1000; 0b1011 & 0b1000 - 0b1000, что является правдой. В позиции 3 находится одна, а arr[3] - в combinationSum.

Сообщите, пожалуйста, j является 2. 1 << j - 0b10; 0b1011 & 0b100 - 0b0, что является фальсификацией. В позиции 2 есть нуль; arr[2] не суммируется.