Subsets

+10

Recibes una lista nums de enteros distintos. Devuelve todos sus subconjuntos, incluido el vacío y la lista completa, de modo que n valores den 2^n subconjuntos. Escribe cada subconjunto con sus valores en orden ascendente y enumera los subconjuntos en orden lexicográfico: compara dos subconjuntos valor por valor; decide la primera diferencia, y si un subconjunto es el comienzo de otro, va antes. Para [1, 2], la respuesta es [[], [1], [1, 2], [2]].

Función

subsets(nums: integer-array) → integer-2d-array

numsinteger-array: los valores, todos distintos, en cualquier orden
Devuelveinteger-2d-array: cada subconjunto, ordenado de menor a mayor y enumerado en orden lexicográfico

Restricciones

1 ≤ nums.length ≤ 10
-10 ≤ nums[i] ≤ 10
Todos los valores de nums son diferentes.
nums puede venir en cualquier orden.

Ejemplos

Entrada: nums = [3, 1, 2]
Salida: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Explicación: Ordenados, los valores son 1, 2, 3, y tres valores dan 2^3 = 8 subconjuntos. [1, 2] va antes que [1, 2, 3] porque es su inicio, y [1, 2, 3] va antes que [1, 3] porque 2 es menor que 3 en la segunda posición.

Entrada: nums = [0]
Salida: [[], [0]]
Explicación: Un valor tiene dos subconjuntos: déjalo fuera y obtén [], o tómalo y obtén [0]. El subconjunto vacío siempre va primero.

Entrada: nums = [5, -2]
Salida: [[], [-2], [-2, 5], [5]]
Explicación: Los valores se ordenan como -2 y 5, así que [-2, 5] se escribe en ese orden. Cada subconjunto que contiene -2 va antes de [5], porque -2 es menor que 5.

+13 pruebas ocultas al enviar

Para ir más allá

¿Puedes generar la misma lista sin recursión, construyendo cada subconjunto directamente a partir del anterior?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Hay 2^n subconjuntos, así que ningún método realiza menos de O(2^n) trabajo. La verdadera pregunta es cómo generar cada subconjunto una sola vez, en el orden requerido, sin ordenar después 1024 listas. El retroceso sobre los valores ordenados, registrando cada nodo del árbol de decisiones al entrar en él, recorre los subconjuntos exactamente en orden lexicográfico.

Máscaras de bits, después ordenar

Intuición

Alinea los valores ordenados en las posiciones de 0 a n-1. Un subconjunto indica sí o no para cada posición, y eso es lo que hacen los n bits de un número. Así que los números del 0 al 2^n-1 representan los subconjuntos: para [1, 2, 3], la máscara 5 es 101 en binario, los bits 0 y 2 están activados y representa [1, 3]. La máscara 0 es el subconjunto vacío y la máscara 7 es la lista completa.

Las distintas máscaras dan subconjuntos distintos y cada subconjunto tiene una máscara, así que el bucle produce los 2^n subconjuntos exactamente una vez. Leer los bits desde la posición 0 hacia arriba sobre los valores ordenados escribe cada subconjunto en orden ascendente.

Las máscaras no aparecen en el orden que pide el problema. La máscara 1 es [1], la máscara 2 es [2] y la máscara 3 es [1, 2], así que [2] quedaría antes de [1, 2]. Lo solucionas con una ordenación cuyo comparador compara valor por valor y coloca primero un prefijo. La ordenación cuesta más que la generación: para 2^n subconjuntos hacen falta alrededor de n × 2^n comparaciones, y cada comparación lee hasta n valores. Para n = 10 son alrededor de 10^5 lecturas, todavía rápido, pero es trabajo que el siguiente enfoque nunca realiza.

Algoritmo

Ordena nums para que cada subconjunto se lea en orden ascendente.
Para cada máscara de 0 a 2^n-1, recopila los valores de las posiciones cuyo bit está activado.
Ordena la lista de subconjuntos: en la primera posición en la que dos difieren, gana el valor menor; si uno se acaba primero, va primero.
Devuelve la lista ordenada.

def subsets(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    for mask in range(1 << n):
        # Bit i of mask says whether values[i] is in this subset.
        result.append([values[i] for i in range(n) if (mask >> i) & 1])
    # Python compares lists position by position, and a prefix comes first.
    result.sort()
    return result

Búsqueda con retroceso: elegir, explorar, deshacer la elección

Intuición

Imagina los subconjuntos como un árbol. La raíz es el subconjunto vacío. Debajo de un nodo puedes añadir cualquier valor que sea mayor que el último que añadiste. Para los valores ordenados [1, 2, 3], la raíz tiene los hijos [1], [2] y [3]; [1] tiene los hijos [1, 2] y [1, 3]; [1, 2] tiene el hijo [1, 2, 3]. Cada subconjunto aparece exactamente una vez en este árbol, porque solo hay una forma de escribirlo en orden ascendente, y cada nodo es una respuesta, no solo las hojas.

El retroceso recorre el árbol con una lista compartida, path. Para bajar a un hijo, eliges: añades el valor. Exploras: haces una llamada recursiva, y la función auxiliar registra una copia de path en el momento en que llega. Después, deshaces la elección: eliminas el valor, de modo que path vuelve a estar en el nodo padre y se puede probar el siguiente hermano. Como cada nodo se registra al entrar, el padre siempre se escribe antes que sus hijos.

Por eso la salida está en orden lexicográfico sin necesidad de ordenar. Los hijos de un nodo se prueban desde el valor más pequeño hacia arriba, y el recorrido completa una rama entera antes de empezar la siguiente. Para [1, 2, 3] registra [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]: el orden de un diccionario, con un prefijo antes que sus extensiones.

El árbol tiene 2^n nodos y copiar una ruta cuesta hasta n, así que el tiempo es O(n × 2^n), el tamaño de la propia respuesta. Además de la salida, se mantienen una ruta y una pila de llamadas, ambas de una profundidad máxima de n.

Algoritmo

Ordena los valores.
Escribe explore(start). Primero agrega una copia de path al resultado.
Después, para cada índice i desde start hasta el final: agrega values[i] a path (elige), llama a explore(i+1) (explora) y elimina el último valor (deselige).
Llama a explore(0) con una ruta vacía y devuelve el resultado.

def subsets(nums):
    values = sorted(nums)
    result = []
    path = []

    def explore(start):
        # Every node of the decision tree is a subset: record it on the way in.
        result.append(path[:])
        for i in range(start, len(values)):
            path.append(values[i])  # choose
            explore(i + 1)          # explore: only larger values may follow
            path.pop()              # un-choose

    explore(0)
    return result

Errores comunes y casos límite

La mayoría de las respuestas incorrectas aquí se deben al orden o a compartir una misma lista.

Agregar path en sí en lugar de una copia. Todas las entradas apuntan entonces a la misma lista, que está vacía cuando termina el recorrido, así que se devuelven 2^n copias de [].
Olvidar ordenar nums. Con [3, 1, 2], el árbol construye [3, 1], que no está en orden ascendente, y el recorrido deja de estar en orden lexicográfico.
Registrar solo en las hojas, como harías con las permutaciones. Cada nodo de este árbol es un subconjunto; registrar solo los caminos que llegan al final devuelve demasiado pocos subconjuntos.
Hacer la recursión con start+1 en lugar de i+1. Así, un valor puede ir después de uno mayor o incluso de sí mismo, y se obtienen listas como [3, 2] y [3, 3], que no son subconjuntos en orden ascendente.
Usar el árbol de inclusión o exclusión (decidir sobre el valor 0, luego el valor 1, y así sucesivamente) y registrar las hojas. Encuentra los 2^n subconjuntos, pero probar primero la inclusión coloca la lista completa al principio, y probar primero la exclusión coloca [3] antes de [2]. Ninguno de los dos órdenes es lexicográfico.
Un comparador que ordena primero por longitud da [], [1], [2], [3], [1, 2], que es un orden diferente.

Preguntas frecuentes4

¿Cuántos subconjuntos tiene un conjunto de n elementos?

2^n. Cada elemento está dentro o fuera, independientemente de los demás, así que las opciones se multiplican: dos para el primer elemento, dos para el segundo, y así sucesivamente. Tres valores dan 8 subconjuntos y diez dan 1024, contando el subconjunto vacío y el conjunto completo.

¿Cuál es la complejidad temporal del problema de los subconjuntos?

O(n × 2^n). Hay 2^n subconjuntos y escribir uno requiere hasta n pasos, así que incluso devolver la respuesta cuesta tanto. El retroceso alcanza este límite y solo utiliza O(n) espacio adicional. Generarlos con máscaras de bits es igual de rápido, pero ordenar el resultado después añade otro factor de n.

¿Debería usar retroceso o máscaras de bits para los subconjuntos?

Las máscaras de bits son breves, no necesitan recursión y hacen visible como bits la elección de incluir o excluir. El retroceso genera los subconjuntos en orden lexicográfico por sí solo y se adapta a las variantes comunes: omitir valores repetidos, considerar solo subconjuntos de tamaño k o solo los que alcanzan una suma objetivo, lo que permite dejar de explorar una rama antes de tiempo.

¿Cómo manejas los valores duplicados en Subsets?

Ordena los valores y, después, en el bucle del asistente de retroceso, omite un valor que sea igual al anterior en el mismo nivel: i > start y values[i] == values[i-1]. La primera copia ya explora todos los subconjuntos que la usan, así que una rama hermana que empiece con la segunda copia solo volvería a crear los mismos subconjuntos.

Python

def subsets(nums):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

nums = [3, 1, 2]

Esperado

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]