Dado un arreglo de enteros nums que puede contener duplicados, la tarea es generar todos los subconjuntos posibles (la potencia del conjunto). Es importante que el conjunto de resultados no contenga subconjuntos duplicados.

Ejemplo:

Entrada: [1,2,2]
Salida:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Solución:

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    const results = [[]]; // Inicializamos con el subconjunto vacío
    const n = nums.length;

    if (n === 0) {
        return results;
    }

    // Ordenamos el arreglo para agrupar elementos duplicados
    nums.sort((a, b) => a - b);

    /**
     * Función de búsqueda en profundidad (DFS) para generar subconjuntos.
     * @param {number} startIndex - Índice de inicio para la selección actual.
     * @param {number[]} currentSubset - El subconjunto que se está construyendo.
     * @param {number} targetSize - El tamaño deseado del subconjunto.
     */
    const dfs = (startIndex, currentSubset, targetSize) => {
        // Si el subconjunto actual alcanza el tamaño deseado, lo agregamos a los resultados.
        if (currentSubset.length === targetSize) {
            results.push([...currentSubset]);
            return;
        }

        // Iteramos desde startIndex para seleccionar elementos.
        for (let i = startIndex; i < n; i++) {
            // Si el elemento actual es igual al anterior y no es el primer elemento de esta iteración, lo saltamos
            // para evitar duplicados en los subconjuntos.
            if (i > startIndex && nums[i] === nums[i - 1]) {
                continue;
            }

            // Incluimos el elemento actual en el subconjunto.
            currentSubset.push(nums[i]);

            // Llamada recursiva para continuar construyendo el subconjunto.
            // Avanzamos el índice de inicio a i + 1.
            dfs(i + 1, currentSubset, targetSize);

            // Backtracking: removemos el último elemento agregado para explorar otras combinaciones.
            currentSubset.pop();
        }
    };

    // Generamos subconjuntos de todos los tamaños posibles, desde 1 hasta n.
    for (let size = 1; size <= n; size++) {
        dfs(0, [], size);
    }

    return results;
};

Enfoque:

Este problema se puede abordar como un problema de combinatoria. Consideremos un arreglo sin duplicados, por ejemplo, [1, 2, 3]. Para generar combinaciones de tamaño 2, tomamos cada elemento y lo combinamos con los elementos que le siguen en el arreglo: [1, 2], [1, 3], [2, 3]. Esto se extiende a la generación de combinaciones de todas las longitudes posibles, desde 1 hasta la longitud del arreglo.

Sin embargo, el problema introduce la complejidad de los elementos duplicados. Para manejar esto de manera efectiva, el primer paso es ordenar el arreglo. Al ordenar, los elementos duplicados se agrupan, lo que facilita su identificación y manejo. Durante el proceso de generación de subconjuntos, si encontramos un elemento que es idéntico al anterior y no es el primer elemento considerado en la iteración actual, debemos omitirlo. Esto asegura que solo se incluya una instancia de un elemento duplicado en una posición particular de un subconjunto, previniendo la generación de subconjuntos idénticos.

La estrategia general implica:

1. Inicializar una lista de resultados con el subconjunto vacío ([]), ya que el conjunto vacío es subconjunto de cualquier conjunto.
2. Obtener la longitud del arreglo de entrada. Si es cero, devolver la lista de resultados inicial.
3. Ordenar el arreglo de entrada.
4. Implementar una función de búsqueda en profundidad (DFS) recursiva:
   • Esta función toma un índice de inicio, el subconjunto actual en construcción y el tamaño objetivo del subconjunto.
   • Se realiza una poda temprana: si el tamaño actual del subconjunto más el número de elemetnos restantes en el areglo es menor que el tamaño objetivo, no es posible formar un subconjunto del tamaño deseado, por lo que la recursión se detiene para esa rama.
   • Si la longitud del subconjunto actual coincide con el tamaño objetivo, se agrega una copia del subconjunto actual a la lista de resultados y se retorna.
   • Se itera desde el índice de inicio hasta el final del arreglo.
   • Se aplica la lógica para saltar elementos duplicados: si el elemento actual es igual al anterior y no es la primera vez que se considera en esta iteración de bucle, se continúa con la siguiente iteración.
   • Se agrega el elemento actual al subconjunto.
   • Se realiza una llamada recursiva a la función DFS, avanzando el índice de inicio a i + 1 para considerar los elementos posteriores.
   • Se realiza el backtracking, eliminando el último elemento agregado al subconjunto para explorar otras posibilidades.
5. Iterar para llamar a la función DFS para cada tamaño de subconjunto posible, desde 1 hasta la longitud del arreglo. La llamada inicial a DFS para cada tamaño se realiza con un índice de inicio de 0, un subconjunto vacío y el tamaño objetivo actual.
6. Finalmente, devolver la lista completa de resultados.