Saltar al contenido

Strings binarios sin unos adyacentes

Fácil#backtracking#pruning~15 min

La misión

Problema

Dada una longitud n, devuelve todos los strings (cadenas) binarios de esa longitud en los que no haya dos 1 seguidos. Devuelve los strings en orden creciente.

Ejemplos

Input:  n = 3
Output: ["000", "001", "010", "100", "101"]
Por qué: 011, 110 y 111 ponen cada uno dos 1 juntos
Input:  n = 1
Output: ["0", "1"]
Input:  n = 0
Output: [""]
Por qué: caso límite: el string vacío es el único string de longitud cero

Pistas

0 / 3

Tiempo objetivo
O(n · 1.62ⁿ)
Espacio objetivo
O(n · 1.62ⁿ)

¿Lo que te frena es la idea y no el código? El árbol de decisión lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio