Проверить разделение массива возможен?

Question

Дан массив A, и нужно понять можно массив разделить на две части, кажый из которых равен 10 -и или нет.

Например при случае A = [-2, 5, 5, 3, 2, 7]

Мы можем иметь эти две подмассивы [-2, 7, 5] и [5, 3, 2] сумма каждой из которых равен 10.

Нужно написать функцию которая получает массив и возвращает true или false в зависимости от того разделение массива возможен или нет.

  function permutDevide(arr) {
    if (arr.length == 1) {
        return false
    }

    if (sum(arr) != 20) {
        return false;
    }
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] + arr[j] == 10) {
                return true
            }
        }
    }
    return false;
}

console.log(permutDevide([10, 5, 5])) // true
console.log(permutDevide([5, 3, 2, -1])) // false
console.log(permutDevide([-2, 5, 5, 3, 2, 7])) // true
console.log(permutDevide([7, 1, 3, 5, 2, 2])) //  true
console.log(permutDevide([1, 1, 10, 1, 1, 6])) // false  но должен возврощать true

Поможете решить задачу?

Answer 1

Могу предложить такое решение! Алгоритм ниже:

PS спасибо @slippyk за исправление!

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

function sum(arr) {
    return arr.reduce((sum, val) => {
        return sum + val
    }, 0)
}

function permutDevide(arr, need = 10) {
    if (arr.length == 1) {
        return false
    }

    if (sum(arr) != need * 2) {
        return false;
    }
    if (arr.includes(need)) return true;
    
    return checkArray(arr, arr[0], 1, need);
}

function checkArray(arr, current, index, need) {
  if (!arr[index]) return false;
  const firstSum = current + arr[index];
  const tempArr = arr.slice(index + 1, arr.length);
  if (firstSum >= 0) {
    if (tempArr.includes(Math.abs(need - firstSum))) return true;
    return checkArray(arr, firstSum, index + 1);
  }
  else {
    if (tempArr.includes(firstSum + need)) return true;
    return checkArray(arr, firstSum, index + 1);
  }
}
console.log(permutDevide([9, 3, 8]))
console.log(permutDevide([10, 5, 5]))
console.log(permutDevide([5, 3, 2, -1])) 
console.log(permutDevide([-2, 5, 5, 3, 2, 7])) 
console.log(permutDevide([7, 1, 3, 5, 2, 2])) 
console.log(permutDevide([1, 1, 10, 1, 1, 6]))

БЛОГ НА HUSL

Проверить разделение массива возможен?

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