0

estoy intentando hacer un ejercicio pero realmente no me da como para hacerlo. Si fuese una suma de los valores internos no habria problema pero este en especifico es un tanto distinto. Alguien me podría ayudar con la solución?

Una función que reciba 2 parámetros, 1.- array numerico, 2.- un numero.

Necesito saber si el numero que me pasan en el 2do parámetro o se encuentra presente en el array o alguuuna de las combinaciones del array te da como suma dicho numero

const sumaNumeroEspecifico = (arr, num) => {
//Si se puede, return true
//si no se puede, return false
}
console.log(sumaNumeroEspecifico([1, 2, 3, 4], 5))

Ej: [1,2,3,4,5], 10 output -> true, porque 5+4+1 = 10

Ej: [1,2,3,4,5], 7 output -> true, porque 5+2 = 7

Ej: [1,2,3,4,5], 1 output -> true, porque 1 se encuentra en el array

Ej: [1,2,3], 7 output -> false, porque no hay combinacion posible que te consiga ese numero

Intente hacerlo con un for anidado, pero finalmente no sirve porque como va tomando 1 numero a la vez, solo termina sumandolos todos

Gracias!

1
  • Esto se trata de formar todas las combinaciones de los elementos del array hasta que sumen el valor del argumento o hasta que no queden más. Primero combinaciones de 2 luego de tres... y así hasta llegar a la suma o acabar de probarlas todas. Ese es el método más básico. que veo.
    – Juan
    el 2 jul. 2021 a las 23:34

4 respuestas 4

2
function isPlusOf(array, target){
    // Validacion basica
    // 1. No es un array valido (array)
    // 2. No es un numero (target)
    if(!(Array.isArray(array) && array.length) || typeof target !== "number"){
        return false;
    }

    return permut(array).some(
      comb => comb.reduce(function (acc, item){
        return (acc === target) ? acc : acc + item
      }, 0) === target
    )
}

// Permutador (consigue todas las combinaciones posibles)
const permut = (arr) => {
    let result = [];

    const permute = (arr, m = []) => {
        if (arr.length === 0) {
            result.push(m)
        } else {
            for (let i = 0; i < arr.length; i++) {
                let curr = arr.slice();
                let next = curr.splice(i, 1);
                permute(curr, m.concat(next))
            }
        }
    }

    permute(arr)
    return result;
}

console.log(isPlusOf([1,2,3], 6)); // true
console.log(isPlusOf([1,2,3], 5)); // true
console.log(isPlusOf([1,2,3], 2)); // true
console.log(isPlusOf([1,2,3,7], 9)); // true

En pocas palabras, de un array como [1,2,3]

Inicialmente se fracciona en [1,2,3] [1,3,2], [3,2,1], [3,1,2] (las combinaciones posibles)

Y luego el reducer va sumando un numero por numero... Esto para leer los numeros en todas las combinaciones posibles y encontrar una combinacion que de el resultado.

1
  • Genial, una logica increible, ni se me habria ocurrido el 6 jul. 2021 a las 17:33
2

Comprendiendo lo que requieres, procedo a dejar lo que realicé,

Ha costado lograrlo, quizá alguien viendolo pueda optimizarlo más, pero creo que se cumple con lo requerido.

Se ve el código extenso, pero realmente es porque se dejó explicado en los comentarios los mas posible

let combinaciones = [];

const sumaNumeroEspecifico = (arr, num) => {

  /**
   * Sumamos todos los item del arreglo suministrados,
   * en caso tal de no cumplir la primer parte del if, se proceda a validar con el total
   */
  const sumaTotal = arr.reduce((a, c) => a + c);

  /**
   * Primero verificamos con la funcion include si el numero recibido existe en alguno de
   * los items del arreglo, de no ser así procedemos a validar la suma de todos los items
   * del arreglo. No es necesario hacerlo, pero considero que es mas optimo hacer la suma
   * y verificar si el total de los items del arreglo es igual al número a validar.
   * 
   * En caso tal de no cumplir el if, procedemos a validar que la suma total de los items
   * sea mayor al numero a verificar, para evitar consumos excesivos de memoria.
   * Si es menor dicha suma, se sabe que no se cumple con la condicion requerida y retornamos false
   * 
   * Si ninguna de las 2 opciones se cumple, procedemos a realizar las combinaciones y verificaciones
   */
  if (arr.includes(num) || sumaTotal === num) {
    return true;
  } else if (sumaTotal < num) {
    return false;
  } else {

    /**
     * En este punto hacemos la ejecucion inicial del metodo encargado de generar
     * todas las combinaciones posibles.
     */
    combinacionesSuma(arr, num, [], 0);

    let result = false;

    // Recorremos la matriz con cada combinacion generada
    for (let i = 0; i < combinaciones.length; i++) {

      /**
       * Desligamos el arreglo suministrado del temporal
       * Esto es para evitar modificar el arreglo principal en cada modificacion del
       * arreglo temporal
       */
      const arrTemp = JSON.parse(JSON.stringify(arr));
      const combo = combinaciones[i];

      /**
       * Procedemos a recorrer el arreglo con los items correspondientes
       * que al sumarlos todos el resultado es el mismo del valor suministrado
       */
      for (let j = 0; j < combo.length; j++) {
        const n = combo[j];

        // Verificamos si el numero o item del arreglo combo existe en el arreglo temporal
        if (arrTemp.includes(n)) {
          // Vamos eliminando cada item del arreglo temporal que exista en el arreglo combo
          arrTemp.splice(arrTemp.indexOf(n), 1);
          // Tambien se elimina el item del arreglo combo
          combo.splice(j, 1);
          /**
           * Se le resta al indice j un digito ya que al remover el item actual,
           * el item siguiente pasa a ocupar su lugar.
           */
          j--;
        }

        /**
         * Si el combo queda vacio es porque todos sus digitos existen
         * en el arreglo suministrado
         * cambiamos a true la variable result y cortamos el ciclo del combo.
         * 
         * Si no entra en el if, validamos si el arreglo temporal se encuentra vacio
         * o validamos si ya el ciclo va a culminar, para inicializar la variable
         * result en false y hacemos nuevamente el break para cortar el ciclo.
         */
        if (combo.length === 0) {
          result = true;
          break;
        } else if (arrTemp.length === 0) {
          result = false;
          break;
        }
      }

      if (result) {
        return true;
      } else if (i === combinaciones.length - 1) {
        return false;
      }
    }
  }
};

/**
 * Creamos metodo recursivo, el cual consiste en generar todas las combinaciones posibles,
 * para que se obtenga el numero a verificar. Estos datos se almacenan en la matriz combinaciones.
 */
function combinacionesSuma(arr, num, combo, sum) {
  if (sum === num) {
    /**
     * Antes de almacenar el arreglo, se hace una transformación a string y se parsea nuevamente,
     * Esto debido a que al hacer posteriores modificaciones y no afectar la ejecución de la recursividad.
     */
    combinaciones.push(JSON.parse(JSON.stringify(combo)));
  } else {
    for (let i = 1; i <= num; i++) {
      sum += i;
      if (sum <= num) {

        /**
         * Agregamos al arreglo combo el valor de i
         */
        combo.push(i);

        /**
         * En esta parte del codigo aplicamos la recursividad, haciendo llamados sobre
         * el mismo metodo, con los ajustes necesarios en la informacion a mandar
         */
        combinacionesSuma(arr, num, combo, sum);

        /**
         * Posterior a la ejecucion del metodo, removemos del arreglo combo el item con el mismo valor de i
         * Esto se realiza para poder tener las combinaciones exactas, en cada arreglo que se va generando
         * el cual al sumar todos sus items va a dar como resultado el numero a validar.
         */
        combo.splice(combo.indexOf(i), 1);
      }

      /**
       * En este punto le restamos a la suma que llevamos el valor de i.
       */
      sum -= i;
    }
  }
}

const arreglo = [1, 2, 3];
console.log(sumaNumeroEspecifico(arreglo, Number(prompt('Ingrese el número a verificar', 0))));

Espero te sirva, Saludos.

2
  • Tremenda respuesta man, te pasaste, muchas gracias por el tiempo y explicación. Efectivamente funciona y si bien me alegra tener la solucion igual es un poco deprimente ya que yo no podria haber llegado a esto solo, una lastima pero asi es el tema. Gracias! el 6 jul. 2021 a las 17:26
  • @Programmer89 tranquilo, me alegro que te halla servido, y no te preocupes. Poco a poco se va avanzando, no cres. Me puso a pensar esa pregunta la solución
    – jGomez
    el 6 jul. 2021 a las 20:58
0

Dado el arreglo [4,2,3,1], imagina que a cada elemento le corresponde una posición de dígito binario:

   +---------- 2^3 = 8
   |  +------- 2^2 = 4
   |  |  +---- 2^1 = 2
   |  |  |  +- 2^0 = 1
   |  |  |  |
   4  3  2  1

Tenemos 2^n combinaciones binarias posibles, y si consideramos que cada dígito binario nos puede indicar si el elemento participa -o no- en la sumatoria encontraríamos estos casos:

   8  4  2  1
-------------
#  4  3  2  1
-------------
6) 0  1  1  0  = 5
9) 1  0  0  1  = 5

En otras palabras, podemos usar el número de combinación binaria (#) como una máscara de inclusión de elementos:

function f( arr, num ){
   for( m=1; m < Math.pow(2,arr.length); m++ ){ // El número de combinaciones es 2^n
      let comb = []; // La combinación de números
      for( i=0; i<arr.length; i++ ) // Evaluamos cada elemento contra la máscara
         if( Math.pow(2,i) & m ) // ¿La posición del elemento cumple con la máscara?
            comb.push(arr[i])
      //console.log( 'Mascara '+m, comb );
      let sum = 0; // La suma de la combinación
      for( i=0; i<comb.length; i++ )
         sum += comb[i];
      if( sum == num )
         console.log('Eureka!', comb);
   }
}

f( [4,3,2,1], 5 );

2
  • Wow, me imagino que debes ser super bueno en matematica, esta solucion no es algo sencillo para una persona que no tiene "dedos para el piano" en mate, me equivoco? el 6 jul. 2021 a las 17:34
  • Músicos profesionales opinan que si eres capaz de hacer "toc-toc" puedes tocar cualquier instrumento. Análogamente, la numeración binaria no es tan difícil; si acaso será cuestión de pensar "fuera de la caja".
    – Sal
    el 6 jul. 2021 a las 19:23
0

esto es una menera mucho más sencilla que encontré:

  function work (arr){
      let target = arr.sort((a,b) => a-b).pop();
      
      return isContains(arr, target);

      function isContains(arr, target){
        if(arr.length === 0){
            return target===0;
        }
        let head = arr[0]
        let tail = arr.slice(1);

        return isContains(tail, target - head) || isContains(tail, target);
      }

  }
  console.log(work([4,6,23,10,1,3]))

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.