Retrocediendo para encontrar todos los subconjuntos

Dado un conjunto de enteros positivos, encuentre todos sus subconjuntos. 

Ejemplos: 

Input: array = {1, 2, 3}
Output: // this space denotes null element. 
         1
         1 2
         1 2 3
         1 3
         2
         2 3
         3
Explanation: These are all the subsets that 
can be formed using the array.

Input: 1 2
Output: 
         1 
         2
         1 2
Explanation: These are all the subsets that 
can be formed using the array.

La solución iterativa ya se discutió aquí: el enfoque iterativo para encontrar todos los subconjuntos . Este artículo tiene como objetivo proporcionar un enfoque de retroceso .

Enfoque: La idea es simple, que si hay n cantidad de elementos dentro de una array, hay n cantidad de opciones para el primer elemento de la array. Pasando a la siguiente llamada de recurrencia, habrá n-1 número de opciones (ya que no podemos insertar el último elemento nuevamente ahora) para insertar el segundo elemento en la array. 
El uso de la idea anterior forma una solución recursiva al problema.

Algoritmo: 

1. Cree una función recursiva que tome los siguientes parámetros, la array de entrada, el índice actual, la array de salida o el subconjunto actual, si todos los subconjuntos deben almacenarse, entonces se necesita un vector de la array si los subconjuntos deben imprimirse solo entonces este espacio puede ser ignorado.
2. Primero, imprima el subconjunto (array de salida) que se ha enviado a la función y luego ejecute un ciclo for comenzando desde el ‘índice’ hasta n-1, donde n es el tamaño de la array de entrada. Usamos un bucle para demostrar que tenemos exactamente n número de opciones para elegir al agregar el primer elemento a nuestra nueva array. 
3. Dentro del bucle, llamamos a la función para el siguiente índice después de insertar ese índice en particular y luego, en la siguiente llamada, nuevamente tenemos (n-1) opciones para elegir y así continúa. 
4. Cada vez que se realiza una llamada para el último índice de la array: en esa llamada de función, el bucle no se ejecuta ya que la condición i<A.size() no se cumple y, por lo tanto, retrocedemos hasta la última llamada recursiva y llamamos a la función. para el siguiente índice después de eliminar el elemento en ese índice actual.

1. Finalmente regresamos cuando finaliza el bucle inicial y hemos recibido todos los subconjuntos posibles. 

Implementación: 

// CPP program to find all subsets by backtracking.
#include <bits/stdc++.h>
using namespace std;
 
// For our vector subset, at every step we have A.size()-i-1
// choices to include. A loop helps us to choose each element
// and then move to the indices further present in the array.
// At the end we backtrack to choose a different index.
void subsetsUtil(vector<int>& A, vector<vector<int> >& res,
                 vector<int>& subset, int index)
{
    res.push_back(subset);
      // Loop to choose from different elements present
      // after the current index 'index'
    for (int i = index; i < A.size(); i++) {
 
        // include the A[i] in subset.
        subset.push_back(A[i]);
 
        // move onto the next element.
        subsetsUtil(A, res, subset, i + 1);
 
        // exclude the A[i] from subset and triggers
        // backtracking.
        subset.pop_back();
    }
 
    return;
}
 
// below function returns the subsets of vector A.
vector<vector<int> > subsets(vector<int>& A)
{
    vector<int> subset;
    vector<vector<int> > res;
 
    // keeps track of current element in vector A
      // and the number of elements present in the array subset
    int index = 0;
    subsetsUtil(A, res, subset, index);
 
    return res;
}
 
// Driver Code.
int main()
{
    // find the subsets of below vector.
    vector<int> array = { 1, 2, 3 };
 
    // res will store all subsets.
    // O(2 ^ (number of elements inside array))
    // because total number of subsets possible
    // are O(2^N)
    vector<vector<int> > res = subsets(array);
 
    // Print result
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++)
            cout << res[i][j] << " ";
        cout << endl;
    }
 
    return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.*;
class GFG {
    public static void
    findSubsets(List<List<Integer>> subset, ArrayList<Integer> nums, ArrayList<Integer> output, int index)
    {
      // Base Condition
        if (index == nums.size()) {
            subset.add(output);
            return;
        }
       
        // Not Including Value which is at Index
        findSubsets(subset, nums, new ArrayList<>(output), index + 1);
 
        // Including Value which is at Index
        output.add(nums.get(index));
        findSubsets(subset, nums, new ArrayList<>(output), index + 1);
    }
 
    public static void main(String[] args) {
       
      //Main List for storing all subsets
      List<List<Integer>> subset = new ArrayList<>();
       
      // Input ArrayList
      ArrayList<Integer> input = new ArrayList<>();
      input.add(1);
      input.add(2);
      input.add(3);
       
      findSubsets(subset, input, new ArrayList<>(), 0);
 
      // Comparator is used so that all subset get
      // sorted in ascending order of values
        Collections.sort(subset, (o1, o2) -> {
            int n = Math.min(o1.size(), o2.size());
            for (int i = 0; i < n; i++) {
                if (o1.get(i) == o2.get(i)){
                    continue;
                }else{
                    return o1.get(i) - o2.get(i);
                }
            }
            return 1;
        });
       
       
      // Printing Subset
      for(int i = 0; i < subset.size(); i++){
          for(int j = 0; j < subset.get(i).size(); j++){
              System.out.print(subset.get(i).get(j) + " ");
          }
          System.out.println();
      }
       
    }
}

# Python3 program to find all subsets
# by backtracking.
 
# In the array A at every step we have two
# choices for each element either we can
# ignore the element or we can include the
# element in our subset
def subsetsUtil(A, subset, index):
    print(*subset)
    for i in range(index, len(A)):
         
        # include the A[i] in subset.
        subset.append(A[i])
         
        # move onto the next element.
        subsetsUtil(A, subset, i + 1)
         
        # exclude the A[i] from subset and
        # triggers backtracking.
        subset.pop(-1)
    return
 
# below function returns the subsets of vector A.
def subsets(A):
    global res
    subset = []
     
    # keeps track of current element in vector A
    index = 0
    subsetsUtil(A, subset, index)
     
# Driver Code
 
# find the subsets of below vector.
array = [1, 2, 3]
 
# res will store all subsets.
# O(2 ^ (number of elements inside array))
# because at every step we have two choices
# either include or ignore.
subsets(array)
 
# This code is contributed by SHUBHAMSINGH8410

/*package whatever //do not write package name here */
using System;
using System.Collections.Generic;
 
public class GFG {
  public static void
    findSubsets(List<List<int>> subset, List<int> nums, List<int> output, int index)
  {
    // Base Condition
    if (index == nums.Count) {
      subset.Add(output);
      return;
    }
 
    // Not Including Value which is at Index
    findSubsets(subset, nums, new List<int>(output), index + 1);
 
    // Including Value which is at Index
    output.Add(nums[index]);
    findSubsets(subset, nums, new List<int>(output), index + 1);
  }
 
  public static void Main(String[] args) {
 
    // Main List for storing all subsets
    List<List<int>> subset = new List<List<int>>();
 
    // Input List
    List<int> input = new List<int>();
    input.Add(1);
    input.Add(2);
    input.Add(3);
 
    findSubsets(subset, input, new List<int>(), 0);
 
    // Comparator is used so that all subset get
    // sorted in ascending order of values
    subset.Sort((o1, o2) => {
      int n = Math.Min(o1.Count, o2.Count);
      for (int i = 0; i < n; i++) {
        if (o1[i] == o2[i]){
          continue;
        }else{
          return o1[i] - o2[i];
        }
      }
      return 1;
    });
 
    // Printing Subset
    for(int i = 0; i < subset.Count; i++){
      for(int j = 0; j < subset[i].Count; j++){
        Console.Write(subset[i][j] + " ");
      }
      Console.WriteLine();
    }
 
  }
}
 
// This code is contributed by shikhasingrajput

<script>
/*package whatever //do not write package name here */
function findSubsets(subset, nums, output, index)
{
 
    // Base Condition
    if (index == nums.length) {
        subset.push(output);
        return;
    }
 
    // Not Including Value which is at Index
    findSubsets(subset, nums, [...output], index + 1);
 
    // Including Value which is at Index
    output.push(nums[index]);
    findSubsets(subset, nums, [...output], index + 1);
}
 
// Main List for storing all subsets
let subset = [];
 
// Input ArrayList
let input = [];
input.push(1);
input.push(2);
input.push(3);
 
findSubsets(subset, input, [], 0);
 
// Comparator is used so that all subset get
// sorted in ascending order of values
subset.sort((o1, o2) => {
    let n = Math.min(o1.length, o2.length);
    for (let i = 0; i < n; i++) {
        if (o1[i] == o2[i]) {
            continue;
        } else {
            return o1[i] - o2[i];
        }
    }
    return 1;
});
 
// Printing Subset
for (let i = 0; i < subset.length; i++) {
    for (let j = 0; j < subset[i].length; j++) {
        document.write(subset[i][j] + " ");
    }
    document.write("<br>");
}
 
// This code is contributed by saurabh_jaiswal.
</script>

1 
1 2 
1 2 3 
1 3 
2 
2 3 
3 

Análisis de Complejidad:  

• Complejidad temporal: O(n. 2^n). El número total de subconjuntos generados es 2 ^ n, por lo que la complejidad del tiempo es O (2 ^ n). Si incluimos el tiempo necesario para copiar el vector de subconjunto en el vector res, el tiempo necesario será igual al tamaño del vector de subconjunto.
• Espacio auxiliar: O(n) Puede haber un máximo de n llamadas recursivas en un momento determinado, lo que consumiría espacio de pila O(n).