Imprimir todas las combinaciones de factores (Formas de factorizar)

Escriba un programa para imprimir todas las combinaciones de factores de un número dado n.

Ejemplos: 

Input : 16
Output :2 2 2 2 
        2 2 4 
        2 8 
        4 4 

Input : 12
Output : 2 2 3
         2 6
         3 4

Para resolver este problema, tomamos una array de arrays de enteros o una lista de listas de enteros para almacenar todas las combinaciones de factores posibles para el n dado. Entonces, para lograr esto, podemos tener una función recursiva que puede almacenar la combinación de factores en cada una de sus iteraciones. Y cada una de esas listas debe almacenarse en la lista de resultados finales.

A continuación se muestra la implementación del enfoque anterior.

2 2 2 2 
2 2 4 
2 8 
4 4 

Otro enfoque:

El siguiente código es un código recursivo puro para imprimir todas las combinaciones de factores:

Utiliza un vector de enteros para almacenar una sola lista de factores y un vector de enteros para almacenar todas las combinaciones de factores. En lugar de usar un ciclo iterativo, usa la misma función recursiva para calcular todas las combinaciones de factores.

// C++ program to print all factors combination
#include <bits/stdc++.h>
using namespace std;
 
// vector of vector for storing
// list of factor combinations
vector<vector<int> > factors_combination;
 
// recursive function
void compute_factors(int current_no, int n, int product,
                     vector<int> single_list)
{
     
    // base case: if the product
    // exceeds our given number;
    // OR
    // current_no exceeds half the given n
    if (current_no > (n / 2) || product > n)
        return;
 
    // if current list of factors
    // is contributing to n
    if (product == n) {
       
        // storing the list
        factors_combination.push_back(single_list);
       
        // into factors_combination
        return;
    }
 
    // including current_no in our list
    single_list.push_back(current_no);
 
    // trying to get required
    // n with including current
    // current_no
    compute_factors(current_no, n, product * current_no,
                    single_list);
 
    // excluding current_no from our list
    single_list.pop_back();
 
    // trying to get required n
    // without including current
    // current_no
    compute_factors(current_no + 1, n, product,
                    single_list);
}
 
// Driver Code
int main()
{
    int n = 16;
 
    // vector to store single list of factors
    // eg. 2,2,2,2 is one of the list for n=16
    vector<int> single_list;
 
    // compute_factors ( starting_no, given_n,
    // our_current_product, vector )
    compute_factors(2, n, 1, single_list);
 
    // printing all possible factors stored in
    // factors_combination
    for (int i = 0; i < factors_combination.size(); i++) {
        for (int j = 0; j < factors_combination[i].size();
             j++)
            cout << factors_combination[i][j] << " ";
        cout << endl;
    }
    return 0;
}
 
// code contributed by Devendra Kolhe

// Java program to print all factors combination
import java.util.*;
 
class GFG{
     
// vector of vector for storing
// list of factor combinations
static Vector<Vector<Integer>> factors_combination =
   new Vector<Vector<Integer>>();
  
// Recursive function
static void compute_factors(int current_no, int n, int product,
                            Vector<Integer> single_list)
{
       
    // base case: if the product
    // exceeds our given number;
    // OR
    // current_no exceeds half the given n
    if (current_no > (n / 2) || product > n)
        return;
   
    // If current list of factors
    // is contributing to n
    if (product == n)
    {
         
        // Storing the list
        factors_combination.add(single_list);
         
        // Printing all possible factors stored in
        // factors_combination
        for(int i = 0; i < factors_combination.size(); i++)
        {
            for(int j = 0; j < factors_combination.get(i).size(); j++)
                System.out.print(factors_combination.get(i).get(j) + " ");
        }
        System.out.println();
        factors_combination = new Vector<Vector<Integer>>();
         
        // Into factors_combination
        return;
    }
   
    // Including current_no in our list
    single_list.add(current_no);
   
    // Trying to get required
    // n with including current
    // current_no
    compute_factors(current_no, n,
                    product * current_no,
                    single_list);
   
    // Excluding current_no from our list
    single_list.remove(single_list.size() - 1);
   
    // Trying to get required n
    // without including current
    // current_no
    compute_factors(current_no + 1, n, product,
                    single_list);
}
 
// Driver code
public static void main(String[] args)
{
    int n = 16;
 
    // Vector to store single list of factors
    // eg. 2,2,2,2 is one of the list for n=16
    Vector<Integer> single_list = new Vector<Integer>();
   
    // compute_factors ( starting_no, given_n,
    // our_current_product, vector )
    compute_factors(2, n, 1, single_list);
}
}
 
// This code is contributed by decode2207

# Python3 program to print all factors combination
 
# vector of vector for storing
# list of factor combinations
factors_combination = []
 
# recursive function
def compute_factors(current_no, n, product, single_list):
    global factors_combination
     
    # base case: if the product
    # exceeds our given number;
    # OR
    # current_no exceeds half the given n
    if ((current_no > int(n / 2)) or (product > n)):
        return
  
    # if current list of factors
    # is contributing to n
    if (product == n):
        # storing the list
        factors_combination.append(single_list)
         
        # printing all possible factors stored in
        # factors_combination
        for i in range(len(factors_combination)):
            for j in range(len(factors_combination[i])):
                print(factors_combination[i][j], end=" ")
        print()
        factors_combination = []
        # into factors_combination
        return
  
    # including current_no in our list
    single_list.append(current_no)
  
    # trying to get required
    # n with including current
    # current_no
    compute_factors(current_no, n, product * current_no, single_list)
  
    # excluding current_no from our list
    single_list.pop()
  
    # trying to get required n
    # without including current
    # current_no
    compute_factors(current_no + 1, n, product, single_list)
 
n = 16
 
# vector to store single list of factors
# eg. 2,2,2,2 is one of the list for n=16
single_list = []
 
# compute_factors ( starting_no, given_n,
# our_current_product, vector )
compute_factors(2, n, 1, single_list)
 
# This code is contributed by ukasp.

// C# program to print all factors combination
using System;
using System.Collections.Generic;
class GFG {
     
    // vector of vector for storing
    // list of factor combinations
    static List<List<int>> factors_combination = new List<List<int>>();
     
    // recursive function
    static void compute_factors(int current_no, int n, int product, List<int> single_list)
    {
          
        // base case: if the product
        // exceeds our given number;
        // OR
        // current_no exceeds half the given n
        if (current_no > (n / 2) || product > n)
            return;
      
        // if current list of factors
        // is contributing to n
        if (product == n) {
             
            // storing the list
            factors_combination.Add(single_list);
            // printing all possible factors stored in
            // factors_combination
            for(int i = 0; i < factors_combination.Count; i++)
            {
                for(int j = 0; j < factors_combination[i].Count; j++)
                Console.Write(factors_combination[i][j] + " ");
            }
            Console.WriteLine();
            factors_combination = new List<List<int>>();
            // into factors_combination
            return;
        }
      
        // including current_no in our list
        single_list.Add(current_no);
      
        // trying to get required
        // n with including current
        // current_no
        compute_factors(current_no, n, product * current_no, single_list);
      
        // excluding current_no from our list
        single_list.RemoveAt(single_list.Count - 1);
      
        // trying to get required n
        // without including current
        // current_no
        compute_factors(current_no + 1, n, product, single_list);
    }
 
  static void Main() {
    int n = 16;
  
    // vector to store single list of factors
    // eg. 2,2,2,2 is one of the list for n=16
    List<int> single_list = new List<int>();
  
    // compute_factors ( starting_no, given_n,
    // our_current_product, vector )
    compute_factors(2, n, 1, single_list);
  }
}
 
// This code is contributed by divyesh072019.

<script>
    // Javascript program to print all factors combination
     
    // vector of vector for storing
    // list of factor combinations
    let factors_combination = [];
     
    // recursive function
    function compute_factors(current_no, n, product, single_list)
    {
        // base case: if the product
        // exceeds our given number;
        // OR
        // current_no exceeds half the given n
        if ((current_no > parseInt(n / 2, 10)) || (product > n))
            return;
 
        // if current list of factors
        // is contributing to n
        if (product == n)
        {
            // storing the list
            factors_combination.push(single_list);
 
            // printing all possible factors stored in
            // factors_combination
            for(let i = 0; i < factors_combination.length; i++)
            {
                for(let j = 0; j < factors_combination[i].length; j++)
                {
                    document.write(factors_combination[i][j] + " ");
                }
            }
            document.write("</br>");
            factors_combination = [];
            // into factors_combination
            return;
        }
 
        // including current_no in our list
        single_list.push(current_no);
 
        // trying to get required
        // n with including current
        // current_no
        compute_factors(current_no, n, product * current_no, single_list);
 
        // excluding current_no from our list
        single_list.pop();
 
        // trying to get required n
        // without including current
        // current_no
        compute_factors(current_no + 1, n, product, single_list);
    }
     
    let n = 16;
  
    // vector to store single list of factors
    // eg. 2,2,2,2 is one of the list for n=16
    let single_list = [];
 
    // compute_factors ( starting_no, given_n,
    // our_current_product, vector )
    compute_factors(2, n, 1, single_list);
 
// This code is contributed by suresh07.
</script>

2 2 2 2 
2 2 4 
2 8 
4 4 

Complejidad de tiempo: O(n ² ), n es el tamaño del vector
Espacio auxiliar: O(n ² ), n es el tamaño del vector

Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.