Categoría: Backtracking

Conteo de posibles arreglos de asientos en la sala de cine para mantener el distanciamiento social

Posted on by Rudeus Greyrat

En tiempos de COVID, una sala de cine debe seguir una regla de distancia social en la que cada dos personas sentadas deben tener al menos 6 pies de distancia entre ellas.  Ejemplos: Entrada: lista = {5, 2, 4, 1, 2}  Salida: 16 Explicación: De acuerdo con la lista dada, los asientos están dispuestos como: … Continue reading «Conteo de posibles arreglos de asientos en la sala de cine para mantener el distanciamiento social»

Programa C++ para imprimir todas las permutaciones de una string dada

Posted on by Rudeus Greyrat

Una permutación también llamada «número de arreglo» u «orden» es un reordenamiento de los elementos de una lista ordenada S en una correspondencia uno a uno con S mismo. ¡Una string de longitud n tiene n! permutación.  Fuente: Mathword ( http://mathworld.wolfram.com/Permutation.html ) A continuación se muestran las permutaciones de la string ABC. ABC ACB BAC BCA … Continue reading «Programa C++ para imprimir todas las permutaciones de una string dada»

Dada una array A[] y un número x, verifique el par en A[] con la suma como x (también conocida como Two Sum) – Part 1

Posted on by Rudeus Greyrat

Escriba un programa que, dado un arreglo A[] de n números y otro número x, determine si existen o no dos elementos en A[] cuya suma sea exactamente x.  Ejemplos:  C++ // C++ program for the above approach #include <bits/stdc++.h>   using namespace std;   // Function to find and print pair bool chkPair(int A[], … Continue reading «Dada una array A[] y un número x, verifique el par en A[] con la suma como x (también conocida como Two Sum) – Part 1»

Imprima todas las permutaciones de una string usando ArrayList

Posted on by Rudeus Greyrat

Dada una string str , la tarea es imprimir todas las permutaciones de str . Una permutación es un arreglo de todo o parte de un conjunto de objetos, con respecto al orden del arreglo. Por ejemplo, las palabras ‘bat’ y ‘tab’ representan dos permutaciones distintas (o arreglos) de una palabra similar de tres letras. Ejemplos:   Entrada: … Continue reading «Imprima todas las permutaciones de una string usando ArrayList»

Imprima todas las combinaciones posibles de palabras del Diccionario usando Trie

Posted on by Rudeus Greyrat

Dada una array de strings arr[] , para cada string de la array, imprima todas las combinaciones posibles de strings que se pueden concatenar para formar esa palabra. Ejemplos: Input: arr[] = [«sam», «sung», «samsung»] Output: sam: sam sung: sung samsung: sam sung samsung String ‘samsung’ can be formed using two different strings from the … Continue reading «Imprima todas las combinaciones posibles de palabras del Diccionario usando Trie»

Conjunto de potencia en orden lexicográfico

Posted on by Rudeus Greyrat

Este artículo trata sobre la generación de conjuntos de potencia en orden lexicográfico. Ejemplos:   Input : abc Output : a ab abc ac b bc c La idea es ordenar la array primero. Después de ordenar, corrige los caracteres uno por uno y genera recursivamente todos los subconjuntos a partir de ellos. Después de cada llamada … Continue reading «Conjunto de potencia en orden lexicográfico»

Encuentre todos los subconjuntos distintos de un conjunto determinado utilizando el enfoque BitMasking

Posted on by Rudeus Greyrat

Dado un conjunto de enteros positivos, encuentre todos sus subconjuntos. El conjunto no puede contener elementos duplicados, por lo que cualquier subconjunto repetido debe considerarse solo una vez en la salida. Ejemplos:  Input: S = {1, 2, 2} Output: {}, {1}, {2}, {1, 2}, {2, 2}, {1, 2, 2} Explanation: The total subsets of given … Continue reading «Encuentre todos los subconjuntos distintos de un conjunto determinado utilizando el enfoque BitMasking»

Dada una array A[] y un número x, verifique el par en A[] con la suma como x (también conocida como Two Sum)

Posted on by Rudeus Greyrat

Escriba un programa que, dado un arreglo A[] de n números y otro número x, determine si existen o no dos elementos en A[] cuya suma sea exactamente x.  Ejemplos:  C++ // C++ program for the above approach #include <bits/stdc++.h>   using namespace std;   // Function to find and print pair bool chkPair(int A[], … Continue reading «Dada una array A[] y un número x, verifique el par en A[] con la suma como x (también conocida como Two Sum)»

Imprime todas las formas posibles de escribir N como suma de dos o más números enteros positivos

Posted on by Rudeus Greyrat

Dado un número entero N , la tarea es imprimir todas las formas posibles en las que N se puede escribir como la suma de dos o más números enteros positivos. Ejemplos:   Entrada: N = 4  Salida:  1 1 1 1  1 1 2  1 3  2 2  Entrada: N = 3  Salida:  1 1 … Continue reading «Imprime todas las formas posibles de escribir N como suma de dos o más números enteros positivos»

Número máximo de strings que se pueden formar con ceros y unos dados

Posted on by Rudeus Greyrat

Dada una lista de strings arr[] de ceros y unos solamente y dos enteros N y M , donde N es el número de 1 y M es el número de 0 . La tarea es encontrar el número máximo de strings de la lista dada de strings que se pueden construir con el número … Continue reading «Número máximo de strings que se pueden formar con ceros y unos dados»