Dada una array de enteros no negativos y un valor de suma, determine si hay un subconjunto del conjunto dado con una suma igual a la suma dada.
Ejemplos:
Input : arr[] = {4, 1, 10, 12, 5, 2},
sum = 9
Output : TRUE
{4, 5} is a subset with sum 9.
Input : arr[] = {1, 8, 2, 5},
sum = 4
Output : FALSE
There exists no subset with sum 4.
Hemos discutido una solución basada en programación dinámica en la publicación a continuación.
Programación Dinámica | Conjunto 25 (Problema de suma de subconjuntos)
La solución discutida anteriormente requiere espacio O (n * suma) y tiempo O (n * suma). Podemos optimizar el espacio. Creamos un subconjunto de array 2D booleano [2] [suma + 1]. Usando la forma de abajo hacia arriba podemos llenar esta tabla. La idea detrás de usar 2 en «subconjunto [2] [suma + 1]» es que para llenar una fila solo se requieren los valores de la fila anterior. Por lo tanto, se utilizan filas alternas haciendo que la primera sea la actual y la segunda la anterior o la primera la anterior y la segunda la actual.
C++
// Returns true if there exists a subset
// with given sum in arr[]
#include <iostream>
using namespace std;
bool isSubsetSum(int arr[], int n, int sum)
{
// The value of subset[i%2][j] will be true
// if there exists a subset of sum j in
// arr[0, 1, ...., i-1]
bool subset[2][sum + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
// A subset with sum 0 is always possible
if (j == 0)
subset[i % 2][j] = true;
// If there exists no element no sum
// is possible
else if (i == 0)
subset[i % 2][j] = false;
else if (arr[i - 1] <= j)
subset[i % 2][j] = subset[(i + 1) % 2]
[j - arr[i - 1]] || subset[(i + 1) % 2][j];
else
subset[i % 2][j] = subset[(i + 1) % 2][j];
}
}
return subset[n % 2][sum];
}
// Driver code
int main()
{
int arr[] = { 6, 2, 5 };
int sum = 7;
int n = sizeof(arr) / sizeof(arr[0]);
if (isSubsetSum(arr, n, sum) == true)
cout <<"There exists a subset with given sum";
else
cout <<"No subset exists with given sum";
return 0;
}
// This code is contributed by shivanisinghss2110
C
// Returns true if there exists a subset
// with given sum in arr[]
#include <stdio.h>
#include <stdbool.h>
bool isSubsetSum(int arr[], int n, int sum)
{
// The value of subset[i%2][j] will be true
// if there exists a subset of sum j in
// arr[0, 1, ...., i-1]
bool subset[2][sum + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
// A subset with sum 0 is always possible
if (j == 0)
subset[i % 2][j] = true;
// If there exists no element no sum
// is possible
else if (i == 0)
subset[i % 2][j] = false;
else if (arr[i - 1] <= j)
subset[i % 2][j] = subset[(i + 1) % 2]
[j - arr[i - 1]] || subset[(i + 1) % 2][j];
else
subset[i % 2][j] = subset[(i + 1) % 2][j];
}
}
return subset[n % 2][sum];
}
// Driver code
int main()
{
int arr[] = { 6, 2, 5 };
int sum = 7;
int n = sizeof(arr) / sizeof(arr[0]);
if (isSubsetSum(arr, n, sum) == true)
printf("There exists a subset with given sum");
else
printf("No subset exists with given sum");
return 0;
}
Java
// Java Program to get a subset with a
// with a sum provided by the user
public class Subset_sum {
// Returns true if there exists a subset
// with given sum in arr[]
static boolean isSubsetSum(int arr[], int n, int sum)
{
// The value of subset[i%2][j] will be true
// if there exists a subset of sum j in
// arr[0, 1, ...., i-1]
boolean subset[][] = new boolean[2][sum + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
// A subset with sum 0 is always possible
if (j == 0)
subset[i % 2][j] = true;
// If there exists no element no sum
// is possible
else if (i == 0)
subset[i % 2][j] = false;
else if (arr[i - 1] <= j)
subset[i % 2][j] = subset[(i + 1) % 2]
[j - arr[i - 1]] || subset[(i + 1) % 2][j];
else
subset[i % 2][j] = subset[(i + 1) % 2][j];
}
}
return subset[n % 2][sum];
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 2, 5 };
int sum = 7;
int n = arr.length;
if (isSubsetSum(arr, n, sum) == true)
System.out.println("There exists a subset with" +
"given sum");
else
System.out.println("No subset exists with" +
"given sum");
}
}
// This code is contributed by Sumit Ghosh
Python
# Returns true if there exists a subset
# with given sum in arr[]
def isSubsetSum(arr, n, sum):
# The value of subset[i%2][j] will be true
# if there exists a subset of sum j in
# arr[0, 1, ...., i-1]
subset = [ [False for j in range(sum + 1)] for i in range(3) ]
for i in range(n + 1):
for j in range(sum + 1):
# A subset with sum 0 is always possible
if (j == 0):
subset[i % 2][j] = True
# If there exists no element no sum
# is possible
else if (i == 0):
subset[i % 2][j] = False
else if (arr[i - 1] <= j):
subset[i % 2][j] = subset[(i + 1) % 2][j - arr[i - 1]] or subset[(i + 1)
% 2][j]
else:
subset[i % 2][j] = subset[(i + 1) % 2][j]
return subset[n % 2][sum]
# Driver code
arr = [ 6, 2, 5 ]
sum = 7
n = len(arr)
if (isSubsetSum(arr, n, sum) == True):
print ("There exists a subset with given sum")
else:
print ("No subset exists with given sum")
# This code is contributed by Sachin Bisht
C#
// C# Program to get a subset with a
// with a sum provided by the user
using System;
public class Subset_sum {
// Returns true if there exists a subset
// with given sum in arr[]
static bool isSubsetSum(int []arr, int n, int sum)
{
// The value of subset[i%2][j] will be true
// if there exists a subset of sum j in
// arr[0, 1, ...., i-1]
bool [,]subset = new bool[2,sum + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
// A subset with sum 0 is always possible
if (j == 0)
subset[i % 2,j] = true;
// If there exists no element no sum
// is possible
else if (i == 0)
subset[i % 2,j] = false;
else if (arr[i - 1] <= j)
subset[i % 2,j] = subset[(i + 1) % 2,j - arr[i - 1]] || subset[(i + 1) % 2,j];
else
subset[i % 2,j] = subset[(i + 1) % 2,j];
}
}
return subset[n % 2,sum];
}
// Driver code
public static void Main()
{
int []arr = { 1, 2, 5 };
int sum = 7;
int n = arr.Length;
if (isSubsetSum(arr, n, sum) == true)
Console.WriteLine("There exists a subset with" +
"given sum");
else
Console.WriteLine("No subset exists with" +
"given sum");
}
}
// This code is contributed by Ryuga
PHP
<?php
// Returns true if there exists a subset
// with given sum in arr[]
function isSubsetSum($arr, $n, $sum)
{
// The value of subset[i%2][j] will be
// true if there exists a subset of
// sum j in arr[0, 1, ...., i-1]
$subset[2][$sum + 1] = array();
for ($i = 0; $i <= $n; $i++)
{
for ($j = 0; $j <= $sum; $j++)
{
// A subset with sum 0 is
// always possible
if ($j == 0)
$subset[$i % 2][$j] = true;
// If there exists no element no
// sum is possible
else if ($i == 0)
$subset[$i % 2][$j] = false;
else if ($arr[$i - 1] <= $j)
$subset[$i % 2][$j] = $subset[($i + 1) % 2]
[$j - $arr[$i - 1]] ||
$subset[($i + 1) % 2][$j];
else
$subset[$i % 2][$j] = $subset[($i + 1) % 2][$j];
}
}
return $subset[$n % 2][$sum];
}
// Driver code
$arr = array( 6, 2, 5 );
$sum = 7;
$n = sizeof($arr);
if (isSubsetSum($arr, $n, $sum) == true)
echo ("There exists a subset with given sum");
else
echo ("No subset exists with given sum");
// This code is contributed by Sach_Code
?>
Javascript
<script>
// Javascript Program to get a subset with a
// with a sum provided by the user
// Returns true if there exists a subset
// with given sum in arr[]
function isSubsetSum(arr, n, sum)
{
// The value of subset[i%2][j] will be true
// if there exists a subset of sum j in
// arr[0, 1, ...., i-1]
let subset = new Array(2);
// Loop to create 2D array using 1D array
for (var i = 0; i < subset.length; i++) {
subset[i] = new Array(2);
}
for (let i = 0; i <= n; i++) {
for (let j = 0; j <= sum; j++) {
// A subset with sum 0 is always possible
if (j == 0)
subset[i % 2][j] = true;
// If there exists no element no sum
// is possible
else if (i == 0)
subset[i % 2][j] = false;
else if (arr[i - 1] <= j)
subset[i % 2][j] = subset[(i + 1) % 2]
[j - arr[i - 1]] || subset[(i + 1) % 2][j];
else
subset[i % 2][j] = subset[(i + 1) % 2][j];
}
}
return subset[n % 2][sum];
}
// driver program
let arr = [ 1, 2, 5 ];
let sum = 7;
let n = arr.length;
if (isSubsetSum(arr, n, sum) == true)
document.write("There exists a subset with" +
"given sum");
else
document.write("No subset exists with" +
"given sum");
// This code is contributed by code_hunt.
</script>
Producción
There exists a subset with given sum
Otro enfoque: para reducir aún más la complejidad del espacio, creamos un subconjunto de array 1D booleana [sum+1]. Usando la forma de abajo hacia arriba podemos llenar esta tabla. La idea es que podemos verificar si la suma hasta la posición «i» es posible, entonces si el elemento actual en la array en la posición j es x, entonces la suma i+x también es posible. Atravesamos la array de suma de atrás hacia adelante para no contar ningún elemento dos veces.
Aquí está el código para el enfoque dado:
C++
#include <iostream>
using namespace std;
bool isPossible(int elements[], int sum, int n)
{
int dp[sum + 1];
// Initializing with 1 as sum 0 is
// always possible
dp[0] = 1;
// Loop to go through every element of
// the elements array
for(int i = 0; i < n; i++)
{
// To change the values of all possible sum
// values to 1
for(int j = sum; j >= elements[i]; j--)
{
if (dp[j - elements[i]] == 1)
dp[j] = 1;
}
}
// If sum is possible then return 1
if (dp[sum] == 1)
return true;
return false;
}
// Driver code
int main()
{
int elements[] = { 6, 2, 5 };
int n = sizeof(elements) / sizeof(elements[0]);
int sum = 7;
if (isPossible(elements, sum, n))
cout << ("YES");
else
cout << ("NO");
return 0;
}
// This code is contributed by Potta Lokesh
Java
import java.io.*;
import java.util.*;
class GFG {
static boolean isPossible(int elements[], int sum)
{
int dp[] = new int[sum + 1];
// initializing with 1 as sum 0 is always possible
dp[0] = 1;
// loop to go through every element of the elements
// array
for (int i = 0; i < elements.length; i++) {
// to change the values of all possible sum
// values to 1
for (int j = sum; j >= elements[i]; j--) {
if (dp[j - elements[i]] == 1)
dp[j] = 1;
}
}
// if sum is possible then return 1
if (dp[sum] == 1)
return true;
return false;
}
public static void main(String[] args) throws Exception
{
int elements[] = { 6, 2, 5 };
int sum = 7;
if (isPossible(elements, sum))
System.out.println("YES");
else
System.out.println("NO");
}
}
Python3
def isPossible(elements, target):
dp = [False]*(target+1)
# initializing with 1 as sum 0 is always possible
dp[0] = True
# loop to go through every element of the elements array
for ele in elements:
# to change the value o all possible sum values to True
for j in range(target, ele - 1, -1):
if dp[j - ele]:
dp[j] = True
# If target is possible return True else False
return dp[target]
# Driver code
arr = [6, 2, 5]
target = 7
if isPossible(arr, target):
print("YES")
else:
print("NO")
# The code is contributed by Arpan.
C#
using System;
class GFG {
static Boolean isPossible(int []elements, int sum)
{
int []dp = new int[sum + 1];
// initializing with 1 as sum 0 is always possible
dp[0] = 1;
// loop to go through every element of the elements
// array
for (int i = 0; i < elements.Length; i++)
{
// to change the values of all possible sum
// values to 1
for (int j = sum; j >= elements[i]; j--) {
if (dp[j - elements[i]] == 1)
dp[j] = 1;
}
}
// if sum is possible then return 1
if (dp[sum] == 1)
return true;
return false;
}
// Driver code
public static void Main(String[] args)
{
int []elements = { 6, 2, 5 };
int sum = 7;
if (isPossible(elements, sum))
Console.Write("YES");
else
Console.Write("NO");
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
function isPossible(elements, sum)
{
var dp = [sum + 1];
// initializing with 1 as sum 0 is always possible
dp[0] = 1;
// loop to go through every element of the elements
// array
for (var i = 0; i < elements.length; i++)
{
// to change the values of all possible sum
// values to 1
for (var j = sum; j >= elements[i]; j--) {
if (dp[j - elements[i]] == 1)
dp[j] = 1;
}
}
// if sum is possible then return 1
if (dp[sum] == 1)
return true;
return false;
}
var elements = [ 6, 2, 5 ];
var sum = 7;
if (isPossible(elements, sum))
document.write("YES");
else
document.write("NO");
// This code is contributed by shivanisinghss2110
</script>
Producción
YES
Complejidad de tiempo: O(N*K) donde N es el número de elementos en la array y K es la suma total.
Complejidad espacial: O(K), ya que se ha tomado K espacio extra.
Este artículo es una contribución de Neelesh (Neelesh_Sinha) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA