Dado un entero positivo n , la tarea es generar todas las formas únicas posibles de representar n como suma de enteros positivos.
Ejemplos:
Entrada: 4
Salida:
4
3 1
2 2
2 1 1
1 1 1 1
Entrada: 3
Salida:
3
2 1
1 1 1
Enfoque: Ya hemos discutido la implementación de la generación de particiones únicas en esta publicación. Esta publicación contiene otra implementación mucho más intuitiva para el problema anterior usando recursividad .
La idea es simple y tiene el mismo enfoque que el que se usa aquí . Tenemos que movernos recursivamente de n a 1 y seguir agregando los números utilizados para formar la suma en la array. Cuando la suma se vuelve igual a n, imprimimos la array y regresamos. Los casos base considerados en la implementación son: remSum == 0: Se forma n requerido, así que imprima la array.
Luego, comenzamos a formar la suma requerida utilizando el número de valor máximo utilizado en la partición anterior. Si ese número se vuelve mayor que n, lo ignoramos; de lo contrario, agregamos ese número a la array y nos movemos recursivamente a la siguiente iteración para formar sum = (remSum – i) y donde el número de valor máximo
que podría usarse es i o menor que i. De esta manera podemos generar las particiones únicas requeridas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Array to store the numbers used
// to form the required sum
int dp[200];
int count = 0;
// Function to print the array which contains
// the unique partitions which are used
// to form the required sum
void print(int idx)
{
for (int i = 1; i < idx; i++) {
cout << dp[i] << " ";
}
cout << endl;
}
// Function to find all the unique partitions
// remSum = remaining sum to form
// maxVal is the maximum number that
// can be used to make the partition
void solve(int remSum, int maxVal, int idx, int& count)
{
// If remSum == 0 that means the sum
// is achieved so print the array
if (remSum == 0) {
print(idx);
count++;
return;
}
// i will begin from maxVal which is the
// maximum value which can be used to form the sum
for (int i = maxVal; i >= 1; i--) {
if (i > remSum) {
continue;
}
else if (i <= remSum) {
// Store the number used in forming
// sum gradually in the array
dp[idx] = i;
// Since i used the rest of partition
// cant have any number greater than i
// hence second parameter is i
solve(remSum - i, i, idx + 1, count);
}
}
}
// Driver code
int main()
{
int n = 4, count = 0;
solve(n, n, 1, count);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Array to store the numbers used
// to form the required sum
static int[] dp = new int[200];
static int count = 0;
// Function to print the array which contains
// the unique partitions which are used
// to form the required sum
static void print(int idx)
{
for (int i = 1; i < idx; i++)
{
System.out.print(dp[i] + " ");
}
System.out.println("");
}
// Function to find all the unique partitions
// remSum = remaining sum to form
// maxVal is the maximum number that
// can be used to make the partition
static void solve(int remSum, int maxVal,
int idx, int count)
{
// If remSum == 0 that means the sum
// is achieved so print the array
if (remSum == 0)
{
print(idx);
count++;
return;
}
// i will begin from maxVal which is the
// maximum value which can be used to form the sum
for (int i = maxVal; i >= 1; i--)
{
if (i > remSum)
{
continue;
}
else if (i <= remSum)
{
// Store the number used in forming
// sum gradually in the array
dp[idx] = i;
// Since i used the rest of partition
// cant have any number greater than i
// hence second parameter is i
solve(remSum - i, i, idx + 1, count);
}
}
}
// Driver code
public static void main(String[] args)
{
int n = 4, count = 0;
solve(n, n, 1, count);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python 3 implementation of the approach
# Array to store the numbers used
# to form the required sum
dp = [0 for i in range(200)]
count = 0
# Function to print the array which contains
# the unique partitions which are used
# to form the required sum
def print1(idx):
for i in range(1,idx,1):
print(dp[i],end = " ")
print("\n",end = "")
# Function to find all the unique partitions
# remSum = remaining sum to form
# maxVal is the maximum number that
# can be used to make the partition
def solve(remSum,maxVal,idx,count):
# If remSum == 0 that means the sum
# is achieved so print the array
if (remSum == 0):
print1(idx)
count += 1
return
# i will begin from maxVal which is the
# maximum value which can be used to form the sum
i = maxVal
while(i >= 1):
if (i > remSum):
i -= 1
continue
elif (i <= remSum):
# Store the number used in forming
# sum gradually in the array
dp[idx] = i
# Since i used the rest of partition
# cant have any number greater than i
# hence second parameter is i
solve(remSum - i, i, idx + 1, count)
i -= 1
# Driver code
if __name__ == '__main__':
n = 4
count = 0
solve(n, n, 1, count)
# This code is contributed by
# Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
// Array to store the numbers used
// to form the required sum
static int[] dp = new int[200];
// Function to print the array which contains
// the unique partitions which are used
// to form the required sum
static void print(int idx)
{
for (int i = 1; i < idx; i++)
{
Console.Write(dp[i] + " ");
}
Console.WriteLine("");
}
// Function to find all the unique partitions
// remSum = remaining sum to form
// maxVal is the maximum number that
// can be used to make the partition
static void solve(int remSum, int maxVal,
int idx, int count)
{
// If remSum == 0 that means the sum
// is achieved so print the array
if (remSum == 0)
{
print(idx);
count++;
return;
}
// i will begin from maxVal which is the
// maximum value which can be used to form the sum
for (int i = maxVal; i >= 1; i--)
{
if (i > remSum)
{
continue;
}
else if (i <= remSum)
{
// Store the number used in forming
// sum gradually in the array
dp[idx] = i;
// Since i used the rest of partition
// cant have any number greater than i
// hence second parameter is i
solve(remSum - i, i, idx + 1, count);
}
}
}
// Driver code
public static void Main()
{
int n = 4, count = 0;
solve(n, n, 1, count);
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// JavaScript implementation of the approach
// Array to store the numbers used
// to form the required sum
var dp = Array.from({length: 200}, (_, i) => 0);
var count = 0;
// Function to print the array which contains
// the unique partitions which are used
// to form the required sum
function print(idx)
{
for (var i = 1; i < idx; i++)
{
document.write(dp[i] + " ");
}
document.write('<br>');
}
// Function to find all the unique partitions
// remSum = remaining sum to form
// maxVal is the maximum number that
// can be used to make the partition
function solve(remSum , maxVal,idx , count)
{
// If remSum == 0 that means the sum
// is achieved so print the array
if (remSum == 0)
{
print(idx);
count++;
return;
}
// i will begin from maxVal which is the
// maximum value which can be used to form the sum
for (var i = maxVal; i >= 1; i--)
{
if (i > remSum)
{
continue;
}
else if (i <= remSum)
{
// Store the number used in forming
// sum gradually in the array
dp[idx] = i;
// Since i used the rest of partition
// cant have any number greater than i
// hence second parameter is i
solve(remSum - i, i, idx + 1, count);
}
}
}
// Driver code
var n = 4, count = 0;
solve(n, n, 1, count);
// This code contributed by Princi Singh
</script>
Producción:
4 3 1 2 2 2 1 1 1 1 1 1