Dado un entero positivo N , la tarea es imprimir todas las sumas posibles de cuadrados perfectos de manera que la suma total de todos los cuadrados perfectos sea igual a N.
Ejemplo:
Entrada: N=8
Salida: 4 4
1 1 1 1 4
1 1 1 1 1 1 1 1
Explicación: Hay tres formas posibles de hacer que la suma sea igual a NEntrada: N=3
Salida: 1 1 1
Enfoque: El problema dado se puede resolver usando recursividad y retroceso . La idea es generar una lista de cuadrados perfectos menores que N , luego calcular las posibles combinaciones de suma de cuadrados perfectos que son iguales a N. En la función recursiva, en cada índice, el elemento puede elegirse para la lista o no elegirse . Siga los pasos a continuación para resolver el problema:
- Inicialice una ArrayList para almacenar todos los cuadrados perfectos menores que N
- Iterar el entero N desde 1 hasta la raíz cuadrada de N usando la variable i
- Si el cuadrado de i es menor o igual que N, agregue i * i a la lista
- Use recursividad y retroceso para calcular la suma de cuadrados perfectos que son iguales a N
- En cada índice, haga lo siguiente:
- No incluya el elemento en el índice actual y realice una llamada recursiva al siguiente índice
- Incluya el elemento en el índice actual y realice una llamada recursiva en el mismo índice
- Se necesitarán los siguientes dos casos base para la función recursiva:
- Si N se vuelve menor que cero, o si ind llegó al final de la lista, entonces regrese
- Si N se vuelve igual a cero, imprima la lista
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print all combinations of
// sum of perfect squares equal to N
void combinationSum(
vector<int> list, int N,
int ind, vector<int> perfSquares)
{
// Sum of perfect squares exceeded N
if (N < 0 || ind == list.size())
return;
// Sum of perfect squares is equal to N
// therefore a combination is found
if (N == 0)
{
for (int i : perfSquares)
{
cout << i << " ";
}
cout << endl;
return;
}
// Do not include the current element
combinationSum(list, N,
ind + 1, perfSquares);
// Include the element at current index
perfSquares.push_back(list[ind]);
combinationSum(list, N - list[ind],
ind, perfSquares);
// Remove the current element
perfSquares.pop_back();
}
// Function to check whether the
// number is a perfect square or not
void sumOfPerfectSquares(int N)
{
// Initialize an arraylist to store
// all perfect squares less than N
vector<int> list;
int sqrtN = (int)(sqrt(N));
// Iterate till square root of N
for (int i = 1; i <= sqrtN; i++)
{
// Add all perfect squares
// to the list
list.push_back(i * i);
}
vector<int> perfSquares;
combinationSum(list, N, 0,
perfSquares);
}
// Driver code
int main()
{
int N = 8;
// Call the function
sumOfPerfectSquares(N);
return 0;
}
// This code is contributed by Potta Lokesh
Java
// Java implementation for the above approach
import java.io.*;
import java.util.*;
import java.lang.Math;
class GFG {
// Function to check whether the
// number is a perfect square or not
public static void
sumOfPerfectSquares(int N)
{
// Initialize an arraylist to store
// all perfect squares less than N
ArrayList<Integer> list = new ArrayList<>();
int sqrtN = (int)(Math.sqrt(N));
// Iterate till square root of N
for (int i = 1; i <= sqrtN; i++) {
// Add all perfect squares
// to the list
list.add(i * i);
}
combinationSum(list, N, 0,
new ArrayList<>());
}
// Function to print all combinations of
// sum of perfect squares equal to N
static void combinationSum(
List<Integer> list, int N,
int ind, List<Integer> perfSquares)
{
// Sum of perfect squares exceeded N
if (N < 0 || ind == list.size())
return;
// Sum of perfect squares is equal to N
// therefore a combination is found
if (N == 0) {
for (int i : perfSquares) {
System.out.print(i + " ");
}
System.out.println();
return;
}
// Do not include the current element
combinationSum(list, N,
ind + 1, perfSquares);
// Include the element at current index
perfSquares.add(list.get(ind));
combinationSum(list, N - list.get(ind),
ind, perfSquares);
// Remove the current element
perfSquares.remove(perfSquares.size() - 1);
}
// Driver code
public static void main(String[] args)
{
int N = 8;
// Call the function
sumOfPerfectSquares(N);
}
}
Python3
# Python code for the above approach
# Function to print all combinations of
# sum of perfect squares equal to N
import math
def combinationSum(lst, N, ind, perfSquares):
# Sum of perfect squares exceeded N
if N < 0 or ind == len(lst):
return
# Sum of perfect squares is equal to N
# therefore a combination is found
if N == 0:
for i in perfSquares:
print(i, end = ' ')
print('')
return;
# Do not include the current element
combinationSum(lst,N,ind+1,perfSquares)
# Include the element at current index
perfSquares.append(lst[ind])
combinationSum(lst, N - lst[ind], ind, perfSquares)
# Remove the current element
perfSquares.pop()
# Function to check whether the
# number is a perfect square or not
def sumOfPerfectSquares(N):
# Initialize an arraylist to store
# all perfect squares less than N
lst = []
sqrtN = int(math.sqrt(N))
# Iterate till square root of N
for i in range(1, sqrtN + 1):
# Add all perfect squares
# to the list
lst.append(i*i)
perfSquares = []
combinationSum(lst, N, 0, perfSquares)
# Driver code
N = 8
# Call the function
sumOfPerfectSquares(N)
# This code is contributed by rdtank.
C#
// C# implementation for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to check whether the
// number is a perfect square or not
public static void sumOfPerfectSquares(int N)
{
// Initialize an arraylist to store
// all perfect squares less than N
List<int> list = new List<int>();
int sqrtN = (int)(Math.Sqrt(N));
// Iterate till square root of N
for (int i = 1; i <= sqrtN; i++) {
// Add all perfect squares
// to the list
list.Add(i * i);
}
combinationSum(list, N, 0, new List<int>());
}
// Function to print all combinations of
// sum of perfect squares equal to N
static void combinationSum(List<int> list, int N,
int ind,
List<int> perfSquares)
{
// Sum of perfect squares exceeded N
if (N < 0 || ind == list.Count)
return;
// Sum of perfect squares is equal to N
// therefore a combination is found
if (N == 0) {
foreach(int i in perfSquares)
{
Console.Write(i + " ");
}
Console.WriteLine();
return;
}
// Do not include the current element
combinationSum(list, N, ind + 1, perfSquares);
// Include the element at current index
perfSquares.Add(list[ind]);
combinationSum(list, N - list[ind], ind,
perfSquares);
// Remove the current element
perfSquares.RemoveAt(perfSquares.Count - 1);
}
// Driver code
public static void Main(string[] args)
{
int N = 8;
// Call the function
sumOfPerfectSquares(N);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript code for the above approach
// Function to print all combinations of
// sum of perfect squares equal to N
function combinationSum(list, N, ind, perfSquares)
{
// Sum of perfect squares exceeded N
if (N < 0 || ind == list.length)
return;
// Sum of perfect squares is equal to N
// therefore a combination is found
if (N == 0)
{
for (let i = 0; i < perfSquares.length; i++)
{
document.write(perfSquares[i] + " ");
}
document.write("\n");
return;
}
// Do not include the current element
combinationSum(list, N,
ind + 1, perfSquares);
// Include the element at current index
perfSquares.push(list[ind]);
combinationSum(list, N - list[ind],
ind, perfSquares);
// Remove the current element
perfSquares.pop();
}
// Function to check whether the
// number is a perfect square or not
function sumOfPerfectSquares(N)
{
// Initialize an arraylist to store
// all perfect squares less than N
let list = [];
let sqrtN = Math.sqrt(N);
// Iterate till square root of N
for (let i = 1; i <= sqrtN; i++)
{
// Add all perfect squares
// to the list
list.push(i * i);
}
let perfSquares = [];
combinationSum(list, N, 0,
perfSquares);
}
// Driver code
let N = 8;
// Call the function
sumOfPerfectSquares(N);
// This code is contributed by Samim Hossain Mondal.
</script>
Producción
4 4 1 1 1 1 4 1 1 1 1 1 1 1 1
Complejidad de tiempo: O(N * 2^N), donde N es el número dado
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA