Найти все подмассивы с суммой, равной числу?

Ответ 1

Вы можете выполнить итерацию массива и взять следующий элемент или, если элемент не взят, прежде чем пропустить этот элемент.

function getSubset(array, sum) {
    function iter(temp, delta, index) {
        if (!delta) result.push(temp);
        if (index >= array.length) return;
        iter(temp.concat(array[index]), delta - array[index], index + 1);
        if (!temp.length) iter(temp, delta, index + 1);
    }

    var result = [];
    iter([], sum, 0);
    return result;
}

console.log(getSubset([2, 4, 45, 6, 0, 19], 51));                   // [2, 4, 45], [45, 6], [45, 6, 0]
console.log(getSubset([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280]
console.log(getSubset([1, 3, 6, 11, 1, 5, 4], 4));                  // [1, 3], [4]

Ответ 2

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

Я прокомментировал код для уточнения.

var arr = [1, 3, 6, 11, 1, 5,4];	//  Define array

var target = 31;	//  Define target

//  filter the numbers higher than target and sort rest ascending
var withinRange = arr.filter(x => x <= target).sort((a, b) => a - b);
                      
if(arr.reduce((a,b) => a + b) < target)	//  Check if we have enough numbers to make up that number
  throw "The max you can get out of your selection is: " + arr.reduce((a,b) => a + b);
                      
//  grab the highest number as a starting point and remove it from our array of numbers
var numbers = [withinRange.pop()];

var toFind = target - getSum();	//  get remainder to find

for(var i = withinRange.length - 1; i > -1; i--)	//  iterate from the top
{

  if(toFind == withinRange[i]){	//  check if number is exactly what we need
    numbers.push(withinRange[i]);
    break;
  }else if(withinRange[i] <= toFind){	//  if number is smaller than what we look for
    numbers.push(withinRange[i]);
    toFind -= withinRange[i];
  }

}

function getSum(){	//  sum up our found numbers
  if(numbers.length == 0) return 0;
  return numbers.reduce((a,b) => a + b);
}

console.log([numbers, [target]]);	//  print numbers as desired output
console.log(target, getSum())	//  print the target and our numbers

Ответ 3

Это будет пытаться каждую возможную перестановку массива (остановит дальнейшие перестановки, как только предел достигнут)

function test(arr, num) {
  // sorting will improve time as larger values will be eliminated first
  arr = arr.sort(function(a, b) {
    return b - a;
  });
  var allLists = [];
  var start = Date.now();
  helper(0, 0, []);
  console.log("Ms elapesed: " + (Date.now() - start));
  return allLists || "Not found";

  function helper(start, total, list) {
    var result = [];
    // Using for loop is faster because you can start from desired index without using filter, slice, splice ...
    for (var index = start; index < arr.length; index++) {
      var item = arr[index];
      // If the total is too large the path can be skipped alltogether
      if (total + item <= num) {
        // Check lists if number was not included
        var test = helper(index + 1, total, list.concat(result)); // remove for efficiency
        total += item;
        result.push(item);
        //if (total === num) index = arr.length; add for efficiency
      }
    }
    if (total === num) allLists.push(list.concat(result));
  }
}



console.log(test([2, 4, 45, 6, 0, 19], 51)); // [2,4,45] [2,4,45,0] [6,45] [6,45,0]
console.log(test([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280] [280,0]

Ответ 4

Это даст все доступные дела. И я использую тестовый случай @Nina Scholz

const sum = arr => arr.reduce((a,b) => a + b)

function cal(arr, x) {
  const rs = []
  for (let i = 0; i< arr.length; i++) {
    const tmp = []
    for (let j=i; j<arr.length; j++ ) {
      tmp.push(arr[j])
      if(sum(tmp) === x) rs.push([...tmp])
    }
  }
  return rs
}


console.log(cal([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)) // -> [280]
console.log(cal([2, 4, 45, 6, 0, 19], 51)); // -> [2, 4, 45] [45, 6] [45, 6, 0]
console.log(cal([1, 3, 6, 11, 1, 5, 4], 4)); // -> [1,3] [4]

Ответ 5

Если вопрос заключается в том, чтобы найти все подмножества (а не подмассивы) с заданной перекрестной суммой, это также называется проблемой идеальной суммы. https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/

// A recursive function to print all subsets with the 
// help of dp[][]. Vector p[] stores current subset. 
function printSubsetsRec(arr, i, sum, p) 
{ 
    // If we reached end and sum is non-zero. We print 
    // p[] only if arr[0] is equal to sun OR dp[0][sum] 
    // is true. 
    if (i == 0 && sum != 0 && dp[0][sum]) 
    { 
        p.push(arr[i]); 
        console.log(p); 
        return; 
    } 

    // If sum becomes 0 
    if (i == 0 && sum == 0) 
    { 
        console.log(p); 
        return; 
    } 

    // If given sum can be achieved after ignoring 
    // current element. 
    if (dp[i-1][sum]) 
    { 
        // Create a new vector to store path 
        var b = p.slice(0); 
        printSubsetsRec(arr, i-1, sum, b); 
    } 

    // If given sum can be achieved after considering 
    // current element. 
    if (sum >= arr[i] && dp[i-1][sum-arr[i]]) 
    { 
        p.push(arr[i]); 
        printSubsetsRec(arr, i-1, sum-arr[i], p); 
    } 
} 

// Prints all subsets of arr[0..n-1] with sum 0. 
function printAllSubsets(arr, sum) 
{ 
    var n = arr.length
    if (n == 0 || sum < 0) 
       return; 

    // Sum 0 can always be achieved with 0 elements 
    dp = []; 
    for (var i=0; i<n; ++i) 
    { 
        dp[i] = []
        dp[i][0] = true; 
    } 

    // Sum arr[0] can be achieved with single element 
    if (arr[0] <= sum) 
       dp[0][arr[0]] = true; 

    // Fill rest of the entries in dp[][] 
    for (var i = 1; i < n; ++i) 
        for (var j = 0; j < sum + 1; ++j) 
            dp[i][j] = (arr[i] <= j) ? dp[i-1][j] || 
                                       dp[i-1][j-arr[i]] 
                                     : dp[i - 1][j]; 
    if (dp[n-1][sum] == false) 
    { 
        console.log("There are no subsets with sum %d\n", sum); 
        return; 
    } 

    // Now recursively traverse dp[][] to find all 
    // paths from dp[n-1][sum] 
    var p = []; 
    printSubsetsRec(arr, n-1, sum, p); 
} 

printAllSubsets([1,2,3,4,5], 10); 

Ответ 6

Решение

'use strict';

function print(arr[], i, j) {
   let k = 0;
   for (k = i; k <= j; k += 1) {
     console.log(arr[k]);
   }
}

function findSubArrays(arr[], sum) {
  let n = arr.length;
  let i;
  let j;
  let sum_so_far;

  for (i = 0; i<n; i+= 1) {
    sum_so_far = 0;
    for (j = i; j < n; j++) {
      sum_so_far += arr[j];

      if (sum_so_far === sum) {
         print(arr, i, j);
      }
    }

  }
}

Ответ 7

Я бы сначала цикл в зависимости от размера ожидаемых массивов.

После этого цикла ищем первую часть массива, которая должна быть заполнена позициями, которые будут соответствовать нужному номеру.

Например, для x = 4, имеющего arr = [5,4,32,8,2,1,2,2,3,4,4], сначала нужно взять 4. Вывод начнется с [[4], [4], [4],.....] для позиций 1,9,10 (соответственно)

Затем перейдите к массивам результирующей суммы из 2 элементов [... [2,2], [2,2], [2,2], [1,3]...] (позиции 4 + 6, позиция 4+ 7 position6 + 7 и position 5 + 8) Возможно, вы захотите использовать другую функцию для суммирования и проверки на этом этапе.

Теперь сделаем то же самое для суммы из 3 элементов (если есть) и т.д., Установив максимальный цикл равным номеру исходного массива (итоговое число может быть суммой всех элементов в массиве).

Результирующий пример будет [[4], [4], [4], [2,2], [2,2], [2,2], [1,3]]

Ответ 8

function combinations(array) {
    return new Array(1 << array.length).fill().map(
        (e1,i) => array.filter((e2, j) => i & 1 << j));
}

function add(acc,a) {
  return acc + a 
}

combinations([2, 4, 45, 6, 0, 19]).filter( subarray => subarray.reduce(add, 0)  == 51 )

выход

[[2,4,45],[45,6],[2,4,45,0],[45,6,0]]

combinations([1, 11, 100, 1, 0, 200, 3, 2, 1, 280]).filter( subarray => subarray.reduce(add, 0)  == 280 )

выход

[[280],[0,280]]

Ответ 9

Если бы элементы были строго положительными, такие подпоследовательности можно было бы собрать за один проход, продвигаясь по принципу червя/гусеницы: растягивая переднюю часть, чтобы увеличить сумму (когда она ниже цели), и сжимая ее обратно в Для того чтобы уменьшить сумму:

function worm(arr,target){
  var ret=[];
  var head=0;
  var tail=0;
  var sum=0;
  while(head<arr.length){
    while(sum<=target && head<arr.length){
      sum+=arr[head++];
      if(sum===target)
        ret.push(arr.slice(tail,head));
    }
    while(sum>=target && tail<head){
      sum-=arr[tail++];
      if(sum===target)
        ret.push(arr.slice(tail,head));
    }
  }
  return JSON.stringify(arr)+": "+JSON.stringify(ret);
}

console.log(worm([2, 4, 45, 6, 19], 51));
console.log(worm([1, 11, 100, 1, 200, 3, 2, 1, 280], 280));
console.log(worm([1, 3, 6, 11, 1, 5, 4], 4));

console.log("But it only occasionally finds 0+... / ...+0 sums:");
console.log(worm([2, 4, 45, 6, 0, 19], 51));
console.log(worm([2, 4, 0, 45, 0, 6, 0, 19], 51));
console.log(worm([0, 2, 4, 0, 45, 0, 6, 0, 19], 51));