Dada una array arr[] que consta de N enteros, la tarea es encontrar la suma de todos los subconjuntos de una array , cuya suma es un Número perfecto .
Ejemplos:
Entrada: arr[] = {5, 4, 6}
Salida: 6
Explicación:
Todos los subconjuntos posibles de la array arr[] son:
{5} → Sum = 5
{4} → Sum = 4.
{6} → Sum = 6.
{5, 4} → Suma = 9.
{5, 6} → Suma = 11.
{4, 6} → Suma = 10.
{5, 4, 6} → Suma = 15.
De todas las sumas de subconjuntos, se encuentra que solo 6 sumas son 2` un número perfecto.Entrada: arr[] = {28, 6, 23, 3, 3}
Salida: 28 6 6
Enfoque recursivo : la idea es generar todos los subconjuntos posibles a partir de la array dada e imprimir la suma de esos subconjuntos cuya suma es un número perfecto .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check is a given number
// is a perfect number or not
int isPerfect(int x)
{
// Stores the sum of its divisors
int sum_div = 1;
// Add all divisors of x to sum_div
for (int i = 2; i <= x / 2; ++i) {
if (x % i == 0) {
sum_div += i;
}
}
// If the sum of divisors is equal
// to the given number, return true
if (sum_div == x) {
return 1;
}
// Otherwise, return false
else
return 0;
}
// Function to find sum of all
// subsets from an array whose
// sum is a perfect number
void subsetSum(int arr[], int l,
int r, int sum = 0)
{
// Print the current subset sum
// if it is a perfect number
if (l > r) {
// Check if sum is a
// perfect number or not
if (isPerfect(sum)) {
cout << sum << " ";
}
return;
}
// Calculate sum of the subset
// including arr[l]
subsetSum(arr, l + 1, r, sum + arr[l]);
// Calculate sum of the subset
// excluding arr[l]
subsetSum(arr, l + 1, r, sum);
}
// Driver Code
int main()
{
int arr[] = { 5, 4, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
subsetSum(arr, 0, N - 1);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to check is a given number
// is a perfect number or not
static int isPerfect(int x)
{
// Stores the sum of its divisors
int sum_div = 1;
// Add all divisors of x to sum_div
for(int i = 2; i <= x / 2; ++i)
{
if (x % i == 0)
{
sum_div += i;
}
}
// If the sum of divisors is equal
// to the given number, return true
if (sum_div == x)
{
return 1;
}
// Otherwise, return false
else
return 0;
}
// Function to find sum of all
// subsets from an array whose
// sum is a perfect number
static void subsetSum(int[] arr, int l,
int r, int sum)
{
// Print the current subset sum
// if it is a perfect number
if (l > r)
{
// Check if sum is a
// perfect number or not
if (isPerfect(sum) != 0)
{
System.out.print(sum + " ");
}
return;
}
// Calculate sum of the subset
// including arr[l]
subsetSum(arr, l + 1, r, sum + arr[l]);
// Calculate sum of the subset
// excluding arr[l]
subsetSum(arr, l + 1, r, sum);
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 5, 4, 6 };
int N = arr.length;
subsetSum(arr, 0, N - 1, 0);
}
}
// This code is contributed by code_hunt
Python3
# Python3 program for the above approach import math # Function to check is a given number # is a perfect number or not def isPerfect(x) : # Stores the sum of its divisors sum_div = 1 # Add all divisors of x to sum_div for i in range(2, (x // 2) + 1) : if (x % i == 0) : sum_div += i # If the sum of divisors is equal # to the given number, return true if (sum_div == x) : return 1 # Otherwise, return false else : return 0 # Function to find sum of all # subsets from an array whose # sum is a perfect number def subsetSum(arr, l, r, sum) : # Print current subset sum # if it is a perfect number if (l > r) : # Check if sum is a # perfect number or not if (isPerfect(sum) != 0) : print(sum, end = " ") return # Calculate sum of the subset # including arr[l] subsetSum(arr, l + 1, r, sum + arr[l]) # Calculate sum of the subset # excluding arr[l] subsetSum(arr, l + 1, r, sum) # Driver Code arr = [ 5, 4, 6 ] N = len(arr) subsetSum(arr, 0, N - 1, 0) # This code is contributed by sanjoy_62.
C#
// C# program for the above approach
using System;
class GFG{
// Function to check is a given number
// is a perfect number or not
static int isPerfect(int x)
{
// Stores the sum of its divisors
int sum_div = 1;
// Add all divisors of x to sum_div
for(int i = 2; i <= x / 2; ++i)
{
if (x % i == 0)
{
sum_div += i;
}
}
// If the sum of divisors is equal
// to the given number, return true
if (sum_div == x)
{
return 1;
}
// Otherwise, return false
else
return 0;
}
// Function to find sum of all
// subsets from an array whose
// sum is a perfect number
static void subsetSum(int[] arr, int l,
int r, int sum = 0)
{
// Print the current subset sum
// if it is a perfect number
if (l > r)
{
// Check if sum is a
// perfect number or not
if (isPerfect(sum) != 0)
{
Console.Write(sum + " ");
}
return;
}
// Calculate sum of the subset
// including arr[l]
subsetSum(arr, l + 1, r, sum + arr[l]);
// Calculate sum of the subset
// excluding arr[l]
subsetSum(arr, l + 1, r, sum);
}
// Driver code
static void Main()
{
int[] arr = { 5, 4, 6 };
int N = arr.Length;
subsetSum(arr, 0, N - 1);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// javascript program for the above approach
// Function to check is a given number
// is a perfect number or not
function isPerfect(x) {
// Stores the sum of its divisors
var sum_div = 1;
// Add all divisors of x to sum_div
for (i = 2; i <= x / 2; ++i) {
if (x % i == 0) {
sum_div += i;
}
}
// If the sum of divisors is equal
// to the given number, return true
if (sum_div == x) {
return 1;
}
// Otherwise, return false
else
return 0;
}
// Function to find sum of all
// subsets from an array whose
// sum is a perfect number
function subsetSum(arr , l , r , sum) {
// Print the current subset sum
// if it is a perfect number
if (l > r) {
// Check if sum is a
// perfect number or not
if (isPerfect(sum) != 0) {
document.write(sum + " ");
}
return;
}
// Calculate sum of the subset
// including arr[l]
subsetSum(arr, l + 1, r, sum + arr[l]);
// Calculate sum of the subset
// excluding arr[l]
subsetSum(arr, l + 1, r, sum);
}
// Driver code
var arr = [ 5, 4, 6 ];
var N = arr.length;
subsetSum(arr, 0, N - 1, 0);
// This code contributed by gauravrajput1
</script>
Producción:
6
Complejidad de Tiempo: O(M * 2 N ), donde M es la suma de los elementos del arreglo arr[] Espacio Auxiliar: O(1)
Enfoque iterativo: dado que hay 2 N subconjuntos posibles de una array de tamaño N , la idea es iterar un bucle de 0 a 2 N – 1 y, para cada número, seleccionar todos los elementos de la array que correspondan a 1 s en la representación binaria de el número actual y luego verifique si la suma de los elementos elegidos es un número perfecto o no . Siga los pasos a continuación para resolver el problema:
- Iterar en el rango [0, 2 N – 1] usando la variable i y realizar los siguientes pasos:
- Inicialice una variable, digamos S con 0 para almacenar la suma del subconjunto actual.
- Recorra el arreglo arr[] usando la variable j y realice los siguientes pasos:
- Si la j -ésima posición se establece en la representación binaria de i , agregue el valor de arr[j ] a S.
- Compruebe si S es un número perfecto o no, si es cierto , imprima el valor de S como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check is a given
// number is a perfect number or not
int isPerfect(int x)
{
// Stores sum of divisors
int sum_div = 1;
// Add all divisors of x to sum_div
for (int i = 2; i <= x / 2; ++i) {
if (x % i == 0) {
sum_div += i;
}
}
// If the sum of divisors is equal
// to the given number, return true
if (sum_div == x) {
return 1;
}
// Otherwise, return false
else
return 0;
}
// Function to find the sum of all the
// subsets from an array whose sum is
// a perfect number
void subsetSum(int arr[], int n)
{
// Stores the total number of
// subsets, i.e. 2 ^ n
long long total = 1 << n;
// Consider all numbers from 0 to 2 ^ n - 1
for (long long i = 0; i < total; i++) {
long long sum = 0;
// Consider array elements from
// positions of set bits in the
// binary representation of n
for (int j = 0; j < n; j++)
if (i & (1 << j))
sum += arr[j];
// If sum of chosen elements
// is a perfect number
if (isPerfect(sum)) {
cout << sum << " ";
}
}
}
// Driver Code
int main()
{
int arr[] = { 5, 4, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
subsetSum(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to check is a given
// number is a perfect number or not
static int isPerfect(int x)
{
// Stores sum of divisors
int sum_div = 1;
// Add all divisors of x to sum_div
for (int i = 2; i <= x / 2; ++i) {
if (x % i == 0) {
sum_div += i;
}
}
// If the sum of divisors is equal
// to the given number, return true
if (sum_div == x) {
return 1;
}
// Otherwise, return false
else
return 0;
}
// Function to find the sum of all the
// subsets from an array whose sum is
// a perfect number
static void subsetSum(int arr[], int n)
{
// Stores the total number of
// subsets, i.e. 2 ^ n
long total = 1 << n;
// Consider all numbers from 0 to 2 ^ n - 1
for (long i = 0; i < total; i++) {
int sum = 0;
// Consider array elements from
// positions of set bits in the
// binary representation of n
for (int j = 0; j < n; j++)
if ((i & (1 << j)) != 0)
sum += arr[j];
// If sum of chosen elements
// is a perfect number
if (isPerfect(sum) != 0) {
System.out.print(sum + " ");
}
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, 4, 6 };
int N = arr.length;
subsetSum(arr, N);
}
}
// This code is contributed by souravghosh0416.
Python3
# Python3 program for the above approach # Function to check is a given # number is a perfect number or not def isPerfect(x): # Stores sum of divisors sum_div = 1 # Add all divisors of x to sum_div for i in range(2, int(x/2 + 1)): if (x % i == 0): sum_div = sum_div + i # If the sum of divisors is equal # to the given number, return true if (sum_div == x): return 1 # Otherwise, return false else: return 0 # Function to find the sum of all the # subsets from an array whose sum is # a perfect number def subsetSum(arr, n): # Stores the total number of # subsets, i.e. 2 ^ n total = 1 << n # Consider all numbers from 0 to 2 ^ n - 1 for i in range(total): sum = 0 # Consider array elements from # positions of set bits in the # binary representation of n for j in range(n): if (i & (1 << j) != 0): sum = sum + arr[j] # If sum of chosen elements # is a perfect number if (isPerfect(sum)): print(sum, " ") # Driver Code arr = [5, 4, 6] N = len(arr) subsetSum(arr, N) # This code is contributed by Dharanendra L V.
C#
// C# program for the above approach
using System;
class GFG{
// Function to check is a given
// number is a perfect number or not
static int isPerfect(int x)
{
// Stores sum of divisors
int sum_div = 1;
// Add all divisors of x to sum_div
for (int i = 2; i <= x / 2; ++i) {
if (x % i == 0) {
sum_div += i;
}
}
// If the sum of divisors is equal
// to the given number, return true
if (sum_div == x) {
return 1;
}
// Otherwise, return false
else
return 0;
}
// Function to find the sum of all the
// subsets from an array whose sum is
// a perfect number
static void subsetSum(int[] arr, int n)
{
// Stores the total number of
// subsets, i.e. 2 ^ n
long total = 1 << n;
// Consider all numbers from 0 to 2 ^ n - 1
for (long i = 0; i < total; i++) {
int sum = 0;
// Consider array elements from
// positions of set bits in the
// binary representation of n
for (int j = 0; j < n; j++)
if ((i & (1 << j)) != 0)
sum += arr[j];
// If sum of chosen elements
// is a perfect number
if (isPerfect(sum) != 0) {
Console.Write(sum + " ");
}
}
}
// Driver Code
static public void Main()
{
int[] arr = { 5, 4, 6 };
int N = arr.Length;
subsetSum(arr, N);
}
}
// This code is contributed by splevel62.
Javascript
<script>
// javascript program for the above approach
// Function to check is a given
// number is a perfect number or not
function isPerfect(x)
{
// Stores sum of divisors
var sum_div = 1;
// Add all divisors of x to sum_div
for (var i = 2; i <= parseInt(x / 2); ++i) {
if (x % i == 0) {
sum_div += i;
}
}
// If the sum of divisors is equal
// to the given number, return true
if (sum_div == x) {
return 1;
}
// Otherwise, return false
else
return 0;
}
// Function to find the sum of all the
// subsets from an array whose sum is
// a perfect number
function subsetSum(arr , n)
{
// Stores the total number of
// subsets, i.e. 2 ^ n
var total = 1 << n;
// Consider all numbers from 0 to 2 ^ n - 1
for (i = 0; i < total; i++) {
var sum = 0;
// Consider array elements from
// positions of set bits in the
// binary representation of n
for (j = 0; j < n; j++)
if ((i & (1 << j)) != 0)
sum += arr[j];
// If sum of chosen elements
// is a perfect number
if (isPerfect(sum) != 0) {
document.write(sum + " ");
}
}
}
// Driver Code
var arr = [ 5, 4, 6 ];
var N = arr.length;
subsetSum(arr, N);
// This code is contributed by 29AjayKumar
</script>
Producción:
6
Complejidad de tiempo: O((N + M) * 2 N ), donde M es la suma de los elementos del arreglo , arr[]
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por patelajeet y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA