Question 228240 in Javascript Question posted in
A very good W3school tutorial can be found here.

Is there a good algorithm in JavaScript to divide array into several parts with the same total?

I got a question for an algorithm to divide a given array into the sub parts.
Here is the scenario.
I have 3 items to ship. Weights of items are [10 lb, 15 lb , 5 lb] I need to calculate cases to package the order.
So for the example case, the possible cases would be

  1. 30 lb // one package
  2. 25 + 5 // two packages
  3. 10 + 20 // two packages
  4. 10 + 15 + 5 // three packages

Therefore, the output should be [ 30, [25,5], [10,20], [10,15,5] ] Can anyone please help me to figure out a good algorithm to simulate this model?

Here is my code

const input = [10, 15, 5];

function divideArray(array, length) {
  const result = [];

  function backtrack(startIndex, currentParts) {
    if (currentParts.length === length) {
      result.push([...currentParts]);
      return;
    }

    for (
      let i = startIndex;
      i <= array.length - length + currentParts.length;
      i++
    ) {
      currentParts.push(array.slice(i, i + length));
      backtrack(i + 1, currentParts);
      currentParts.pop();
    }
  }

  backtrack(0, []);

  return result;
}

const subarrayLength = 2;
const dividedArrays = divideArray(input, subarrayLength);
console.log(dividedArrays);

Thank you!

I’ve tried to write a JS function using a recursion function but no luck

Tags:

2

Answers


  1. 0

    try that fixes:

    const input = [10, 15, 5];

function divideArray(array) {
const result = [];

function backtrack(startIndex, currentParts, remainingWeight) {
    if (startIndex === array.length) {
    if (remainingWeight === 0) {
        result.push([...currentParts]);
    }
    return;
    }

    // Include the current weight in the currentParts array
    if (remainingWeight >= array[startIndex]) {
    currentParts.push(array[startIndex]);
    backtrack(startIndex + 1, currentParts, remainingWeight - array[startIndex]);
    currentParts.pop();
    }

    // Skip the current weight
    backtrack(startIndex + 1, currentParts, remainingWeight);
}

backtrack(0, [], input.reduce((sum, weight) => sum + weight, 0));

return result;
}

const dividedArrays = divideArray(input);
console.log(dividedArrays);
    Login or Signup to reply.
  2. 0

    If I understand you correctly the problem is to find all the ways of grouping objects in a collection.

    In the trivial case (one object:A) the response would be

    [A]

    For two objects A,B the response would be

    [A+B] or [A]+[B]

    For three objects A,B,C the response would be

    [A+B+C] or [A+B]+[C] or [A]+[B+C] or [A+C]+[B] or [A]+[B]+[C]

    Is that a correct understanding of the problem?

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search