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

Есть массив, к примеру:

const arr = [1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 7, 8, 11, 13, 31, 31, 44, 51, 81, 65, 63];

и искомая сумма, целое число, к примеру пусть будет:

const target = prompt("enter number", "52");

Как найти все возможные ряды (массивы) чисел из массива, которые дадут в сумме искомую сумму, не используя дважды одно число из массива?


Ответы (1 шт):

Автор решения: Антон Сибгатулин

https://www.cyberforum.ru/python-tasks/thread2973216.html Списал оттуда ,Списал оттуда ,признаюсь,но там написанно на python а вам нужно на javascript вот я и переписал на js)

лучше используй это конечно

Array.prototype.sum = function() {
    return (!this.length) ? 0 : this.slice(1).sum() +
        ((typeof this[0] == 'number') ? this[0] : 0);
};

function comb_sum(arr, cnt, s) {
    var n = arr.length
    res = 0;

    for (var i = 1; i < 2 ** n + 1; i++) {
        var tmp = new Array()
        var p = 1;
        for (var j = 0; j < n; j++) {
            if (i & p) {
                tmp.push(arr[j]);
            }
            p *= 2;
        }
        if (tmp.sum() == s & tmp.length == cnt) {
            console.log(tmp)
            res += 1;
        }


    }
}

доробатывай,иногда повторяются массивы к примеру

comb_sum([7, 7, 7, 7, 7, 7, 8, 8], 3, 23)

Как использовать?

//первым принимается массив , вторым колво цифр , третьим сумму которую надо набрать данным количеством цифр
//massivChisel , количество слагаемых , сумма
  comb_sum([1, 2, 3, 4, 5, 6, 7, 8], 1, 8)
  comb_sum([1, 2, 3, 4, 5, 6, 7, 8], 2, 8)
  comb_sum([1, 2, 3, 4, 5, 6, 7, 8], 3, 8)
  comb_sum([1, 2, 3, 4, 5, 6, 7, 8], 4, 8)
  comb_sum([1, 2, 3, 4, 5, 6, 7, 8], 5, 8)
  .....
  //и т.д.

так же можно и по другому ,перебрав сразу все:

var arr = [1, 2, 3, 4, 5, 6, 7, 8];
for(var i = 1;i<=arr.length;i++){
 comb_sum(arr, i, 8)
}
→ Ссылка