Как получить комбинацию сумм чисел в массиве - PullRequest
Новая
       6

Как получить комбинацию сумм чисел в массиве

0 голосов
/ 15 октября 2018

У меня есть массив, и я хочу получить все комбинации сумм его номера. 

let arr=[1,2,3,4,5];
1st iteration : 1+2=3,1+3=4, 1+4=5, 1+5=6
and array becomes arr[1,2,3,4,5,6]
2nd iteration : 2+1=3,2+3=5, 2+4=6, 2+5=7
and array becomes arr[1,2,3,4,5,6,7]......

and 1+2+3=6, 1+2+4=7
.
.
.
and 1+2+3+4=10
.
. 
. 
and 1+2+3+4+5=15
and final array becomes =[1,2,3,4,5,6,7,8,9,10,11,15]

Может кто-нибудь помочь мне построить алгоритм для этого?

Вот что ядо сих пор пытался подготовить массив возможных под-массивов arr, но не смог получить все комбинации. 

let arr=[1,2,3,4,5];
    let a=[];
    for(let i=0; i < arr.length; i++){
        for(let j=0; j < arr.length; j++){
            let b=[];
            for( let k=i; k<=j; k++ ){
                b.push(arr[k]);
            }
            a.push(b);

        }
    }
    console.log(a);

1 Ответ

0 голосов
/ 16 октября 2018

Вы можете использовать словарь или ассоциативный массив (которые являются массивами JavaScript), чтобы хранить, какие суммы могут быть получены, используя сумму в качестве индекса и устанавливая для элемента значение «true», аналогично созданию сита;затем вы можете эффективно перебирать этот разреженный массив с помощью for in.

function sums(values) {
    var dictionary = [];
    for (var i in values) {
        var temp = [values[i]];               // start with value by itself
        for (var j in dictionary) {
            temp.push(values[i] + Number(j)); // sum of value and values already in dictionary
        }
        for (var k in temp) {
            dictionary[temp[k]] = true;       // transfer values to dictionary
        }
    }
    var output = [];
    for (var i in dictionary) {
        output.push(Number(i));               // convert dictionary to array of values
    }
    return output;
}
document.write(sums([2,5,11,16]));
...