Pular para o conteúdo

Strings binárias sem 1s adjacentes

Fácil#backtracking#pruning~15 min

A missão

Problema

Dado um tamanho n, retorne todas as strings binárias desse tamanho em que nenhum par de 1s fica lado a lado. Retorne as strings em ordem crescente.

Exemplos

Input:  n = 3
Output: ["000", "001", "010", "100", "101"]
Por quê: 011, 110 e 111 colocam dois 1s lado a lado
Input:  n = 1
Output: ["0", "1"]
Input:  n = 0
Output: [""]
Por quê: edge case: a string vazia é a única string de tamanho zero

Dicas

0 / 3

Tempo-alvo
O(n · 1.62ⁿ)
Espaço-alvo
O(n · 1.62ⁿ)

Travou na ideia, e não no código? A árvore de decisão explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado