Dado un conjunto de enteros no negativos y un valor sum , determine si hay un subconjunto del conjunto dado con sum igual a sum dado .
C++
// A recursive solution for subset sum problem
#include <iostream>
using namespace std;
// Returns true if there is a subset
// of set[] with sum equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0)
return false;
// If last element is greater than sum,
// then ignore it
if (set[n - 1] > sum)
return isSubsetSum(set, n - 1, sum);
/* else, check if sum can be obtained by any
of the following:
(a) including the last element
(b) excluding the last element */
return isSubsetSum(set, n - 1, sum)
|| isSubsetSum(set, n - 1, sum - set[n - 1]);
}
// Driver code
int main()
{
int set[] = { 3, 34, 4, 12, 5, 2 };
int sum = 9;
int n = sizeof(set) / sizeof(set[0]);
if (isSubsetSum(set, n, sum) == true)
cout <<"Found a subset with given sum";
else
cout <<"No subset with given sum";
return 0;
}
// This code is contributed by shivanisinghss2110
C
// A recursive solution for subset sum problem
#include <stdio.h>
// Returns true if there is a subset
// of set[] with sum equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0)
return false;
// If last element is greater than sum,
// then ignore it
if (set[n - 1] > sum)
return isSubsetSum(set, n - 1, sum);
/* else, check if sum can be obtained by any
of the following:
(a) including the last element
(b) excluding the last element */
return isSubsetSum(set, n - 1, sum)
|| isSubsetSum(set, n - 1, sum - set[n - 1]);
}
// Driver code
int main()
{
int set[] = { 3, 34, 4, 12, 5, 2 };
int sum = 9;
int n = sizeof(set) / sizeof(set[0]);
if (isSubsetSum(set, n, sum) == true)
printf("Found a subset with given sum");
else
printf("No subset with given sum");
return 0;
}
Java
// A recursive solution for subset sum
// problem
class GFG {
// Returns true if there is a subset
// of set[] with sum equal to given sum
static boolean isSubsetSum(int set[],
int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0)
return false;
// If last element is greater than
// sum, then ignore it
if (set[n - 1] > sum)
return isSubsetSum(set, n - 1, sum);
/* else, check if sum can be obtained
by any of the following
(a) including the last element
(b) excluding the last element */
return isSubsetSum(set, n - 1, sum)
|| isSubsetSum(set, n - 1, sum - set[n - 1]);
}
/* Driver code */
public static void main(String args[])
{
int set[] = { 3, 34, 4, 12, 5, 2 };
int sum = 9;
int n = set.length;
if (isSubsetSum(set, n, sum) == true)
System.out.println("Found a subset"
+ " with given sum");
else
System.out.println("No subset with"
+ " given sum");
}
}
/* This code is contributed by Rajat Mishra */
Python3
# A recursive solution for subset sum
# problem
# Returns true if there is a subset
# of set[] with sun equal to given sum
def isSubsetSum(set, n, sum):
# Base Cases
if (sum == 0):
return True
if (n == 0):
return False
# If last element is greater than
# sum, then ignore it
if (set[n - 1] > sum):
return isSubsetSum(set, n - 1, sum)
# else, check if sum can be obtained
# by any of the following
# (a) including the last element
# (b) excluding the last element
return isSubsetSum(
set, n-1, sum) or isSubsetSum(
set, n-1, sum-set[n-1])
# Driver code
set = [3, 34, 4, 12, 5, 2]
sum = 9
n = len(set)
if (isSubsetSum(set, n, sum) == True):
print("Found a subset with given sum")
else:
print("No subset with given sum")
# This code is contributed by Nikita Tiwari.
C#
// A recursive solution for subset sum problem
using System;
class GFG {
// Returns true if there is a subset of set[] with sum
// equal to given sum
static bool isSubsetSum(int[] set, int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0)
return false;
// If last element is greater than sum,
// then ignore it
if (set[n - 1] > sum)
return isSubsetSum(set, n - 1, sum);
/* else, check if sum can be obtained
by any of the following
(a) including the last element
(b) excluding the last element */
return isSubsetSum(set, n - 1, sum)
|| isSubsetSum(set, n - 1, sum - set[n - 1]);
}
// Driver code
public static void Main()
{
int[] set = { 3, 34, 4, 12, 5, 2 };
int sum = 9;
int n = set.Length;
if (isSubsetSum(set, n, sum) == true)
Console.WriteLine("Found a subset with given sum");
else
Console.WriteLine("No subset with given sum");
}
}
// This code is contributed by Sam007
PHP
<?php
// A recursive solution for subset sum problem
// Returns true if there is a subset of set
// with sun equal to given sum
function isSubsetSum($set, $n, $sum)
{
// Base Cases
if ($sum == 0)
return true;
if ($n == 0)
return false;
// If last element is greater
// than sum, then ignore it
if ($set[$n - 1] > $sum)
return isSubsetSum($set, $n - 1, $sum);
/* else, check if sum can be
obtained by any of the following
(a) including the last element
(b) excluding the last element */
return isSubsetSum($set, $n - 1, $sum) ||
isSubsetSum($set, $n - 1,
$sum - $set[$n - 1]);
}
// Driver Code
$set = array(3, 34, 4, 12, 5, 2);
$sum = 9;
$n = 6;
if (isSubsetSum($set, $n, $sum) == true)
echo"Found a subset with given sum";
else
echo "No subset with given sum";
// This code is contributed by Anuj_67
?>
Javascript
<script>
// A recursive solution for subset sum problem
// Returns true if there is a subset of set[] with sum
// equal to given sum
function isSubsetSum(set, n, sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0)
return false;
// If last element is greater than sum,
// then ignore it
if (set[n - 1] > sum)
return isSubsetSum(set, n - 1, sum);
/* else, check if sum can be obtained
by any of the following
(a) including the last element
(b) excluding the last element */
return isSubsetSum(set, n - 1, sum)
|| isSubsetSum(set, n - 1, sum - set[n - 1]);
}
let set = [ 3, 34, 4, 12, 5, 2 ];
let sum = 9;
let n = set.length;
if (isSubsetSum(set, n, sum) == true)
document.write("Found a subset with given sum");
else
document.write("No subset with given sum");
// This code is contributed by mukesh07.
</script>
C
// A Dynamic Programming solution
// for subset sum problem
#include <stdio.h>
// Returns true if there is a subset of set[]
// with sum equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
// The value of subset[i][j] will be true if
// there is a subset of set[0..j-1] with sum
// equal to i
bool subset[n + 1][sum + 1];
// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
subset[i][0] = true;
// If sum is not 0 and set is empty,
// then answer is false
for (int i = 1; i <= sum; i++)
subset[0][i] = false;
// Fill the subset table in bottom up manner
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j < set[i - 1])
subset[i][j] = subset[i - 1][j];
if (j >= set[i - 1])
subset[i][j] = subset[i - 1][j]
|| subset[i - 1][j - set[i - 1]];
}
}
/* // uncomment this code to print table
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= sum; j++)
printf ("%4d", subset[i][j]);
printf("\n");
}*/
return subset[n][sum];
}
// Driver code
int main()
{
int set[] = { 3, 34, 4, 12, 5, 2 };
int sum = 9;
int n = sizeof(set) / sizeof(set[0]);
if (isSubsetSum(set, n, sum) == true)
printf("Found a subset with given sum");
else
printf("No subset with given sum");
return 0;
}
// This code is contributed by Arjun Tyagi.
C++
// A Dynamic Programming solution
// for subset sum problem
#include <iostream>
using namespace std;
// Returns true if there is a subset of set[]
// with sum equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
// The value of subset[i][j] will be true if
// there is a subset of set[0..j-1] with sum
// equal to i
bool subset[n + 1][sum + 1];
// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
subset[i][0] = true;
// If sum is not 0 and set is empty,
// then answer is false
for (int i = 1; i <= sum; i++)
subset[0][i] = false;
// Fill the subset table in bottom up manner
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j < set[i - 1])
subset[i][j] = subset[i - 1][j];
if (j >= set[i - 1])
subset[i][j] = subset[i - 1][j]
|| subset[i - 1][j - set[i - 1]];
}
}
/* // uncomment this code to print table
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= sum; j++)
printf ("%4d", subset[i][j]);
cout <<"\n";
}*/
return subset[n][sum];
}
// Driver code
int main()
{
int set[] = { 3, 34, 4, 12, 5, 2 };
int sum = 9;
int n = sizeof(set) / sizeof(set[0]);
if (isSubsetSum(set, n, sum) == true)
cout <<"Found a subset with given sum";
else
cout <<"No subset with given sum";
return 0;
}
// This code is contributed by shivanisinghss2110
Java
// A Dynamic Programming solution for subset
// sum problem
class GFG {
// Returns true if there is a subset of
// set[] with sum equal to given sum
static boolean isSubsetSum(int set[],
int n, int sum)
{
// The value of subset[i][j] will be
// true if there is a subset of
// set[0..j-1] with sum equal to i
boolean subset[][] = new boolean[sum + 1][n + 1];
// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
subset[0][i] = true;
// If sum is not 0 and set is empty,
// then answer is false
for (int i = 1; i <= sum; i++)
subset[i][0] = false;
// Fill the subset table in bottom
// up manner
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
subset[i][j] = subset[i][j - 1];
if (i >= set[j - 1])
subset[i][j] = subset[i][j]
|| subset[i - set[j - 1]][j - 1];
}
}
/* // uncomment this code to print table
for (int i = 0; i <= sum; i++)
{
for (int j = 0; j <= n; j++)
System.out.println (subset[i][j]);
} */
return subset[sum][n];
}
/* Driver code*/
public static void main(String args[])
{
int set[] = { 3, 34, 4, 12, 5, 2 };
int sum = 9;
int n = set.length;
if (isSubsetSum(set, n, sum) == true)
System.out.println("Found a subset"
+ " with given sum");
else
System.out.println("No subset with"
+ " given sum");
}
}
/* This code is contributed by Rajat Mishra */
Python3
# A Dynamic Programming solution for subset
# sum problem Returns true if there is a subset of
# set[] with sun equal to given sum
# Returns true if there is a subset of set[]
# with sum equal to given sum
def isSubsetSum(set, n, sum):
# The value of subset[i][j] will be
# true if there is a
# subset of set[0..j-1] with sum equal to i
subset =([[False for i in range(sum + 1)]
for i in range(n + 1)])
# If sum is 0, then answer is true
for i in range(n + 1):
subset[i][0] = True
# If sum is not 0 and set is empty,
# then answer is false
for i in range(1, sum + 1):
subset[0][i]= False
# Fill the subset table in bottom up manner
for i in range(1, n + 1):
for j in range(1, sum + 1):
if j<set[i-1]:
subset[i][j] = subset[i-1][j]
if j>= set[i-1]:
subset[i][j] = (subset[i-1][j] or
subset[i - 1][j-set[i-1]])
# uncomment this code to print table
# for i in range(n + 1):
# for j in range(sum + 1):
# print (subset[i][j], end =" ")
# print()
return subset[n][sum]
# Driver code
if __name__=='__main__':
set = [3, 34, 4, 12, 5, 2]
sum = 9
n = len(set)
if (isSubsetSum(set, n, sum) == True):
print("Found a subset with given sum")
else:
print("No subset with given sum")
# This code is contributed by
# sahil shelangia.
C#
// A Dynamic Programming solution for
// subset sum problem
using System;
class GFG {
// Returns true if there is a subset
// of set[] with sum equal to given sum
static bool isSubsetSum(int[] set, int n, int sum)
{
// The value of subset[i][j] will be true if there
// is a subset of set[0..j-1] with sum equal to i
bool[, ] subset = new bool[sum + 1, n + 1];
// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
subset[0, i] = true;
// If sum is not 0 and set is empty,
// then answer is false
for (int i = 1; i <= sum; i++)
subset[i, 0] = false;
// Fill the subset table in bottom up manner
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
subset[i, j] = subset[i, j - 1];
if (i >= set[j - 1])
subset[i, j] = subset[i, j]
|| subset[i - set[j - 1], j - 1];
}
}
return subset[sum, n];
}
// Driver code
public static void Main()
{
int[] set = { 3, 34, 4, 12, 5, 2 };
int sum = 9;
int n = set.Length;
if (isSubsetSum(set, n, sum) == true)
Console.WriteLine("Found a subset with given sum");
else
Console.WriteLine("No subset with given sum");
}
}
// This code is contributed by Sam007
PHP
<?php
// A Dynamic Programming solution for
// subset sum problem
// Returns true if there is a subset of
// set[] with sum equal to given sum
function isSubsetSum( $set, $n, $sum)
{
// The value of subset[i][j] will
// be true if there is a subset of
// set[0..j-1] with sum equal to i
$subset = array(array());
// If sum is 0, then answer is true
for ( $i = 0; $i <= $n; $i++)
$subset[$i][0] = true;
// If sum is not 0 and set is empty,
// then answer is false
for ( $i = 1; $i <= $sum; $i++)
$subset[0][$i] = false;
// Fill the subset table in bottom
// up manner
for ($i = 1; $i <= $n; $i++)
{
for ($j = 1; $j <= $sum; $j++)
{
if($j < $set[$i-1])
$subset[$i][$j] =
$subset[$i-1][$j];
if ($j >= $set[$i-1])
$subset[$i][$j] =
$subset[$i-1][$j] ||
$subset[$i - 1][$j -
$set[$i-1]];
}
}
/* // uncomment this code to print table
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= sum; j++)
printf ("%4d", subset[i][j]);
printf("n");
}*/
return $subset[$n][$sum];
}
// Driver code
$set = array(3, 34, 4, 12, 5, 2);
$sum = 9;
$n = count($set);
if (isSubsetSum($set, $n, $sum) == true)
echo "Found a subset with given sum";
else
echo "No subset with given sum";
// This code is contributed by anuj_67.
?>
Javascript
<script>
// A Dynamic Programming solution for subset sum problem
// Returns true if there is a subset of
// set[] with sum equal to given sum
function isSubsetSum(set, n, sum)
{
// The value of subset[i][j] will be
// true if there is a subset of
// set[0..j-1] with sum equal to i
let subset = new Array(sum + 1);
for(let i = 0; i < sum + 1; i++)
{
subset[i] = new Array(sum + 1);
for(let j = 0; j < n + 1; j++)
{
subset[i][j] = 0;
}
}
// If sum is 0, then answer is true
for (let i = 0; i <= n; i++)
subset[0][i] = true;
// If sum is not 0 and set is empty,
// then answer is false
for (let i = 1; i <= sum; i++)
subset[i][0] = false;
// Fill the subset table in bottom
// up manner
for (let i = 1; i <= sum; i++) {
for (let j = 1; j <= n; j++) {
subset[i][j] = subset[i][j - 1];
if (i >= set[j - 1])
subset[i][j] = subset[i][j]
|| subset[i - set[j - 1]][j - 1];
}
}
/* // uncomment this code to print table
for (int i = 0; i <= sum; i++)
{
for (int j = 0; j <= n; j++)
System.out.println (subset[i][j]);
} */
return subset[sum][n];
}
let set = [ 3, 34, 4, 12, 5, 2 ];
let sum = 9;
let n = set.length;
if (isSubsetSum(set, n, sum) == true)
document.write("Found a subset" + " with given sum");
else
document.write("No subset with" + " given sum");
// This code is contributed by decode2207.
</script>
C++
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Taking the matrix as globally
int tab[2000][2000];
// Check if possible subset with
// given sum is possible or not
int subsetSum(int a[], int n, int sum)
{
// If the sum is zero it means
// we got our expected sum
if (sum == 0)
return 1;
if (n <= 0)
return 0;
// If the value is not -1 it means it
// already call the function
// with the same value.
// it will save our from the repetition.
if (tab[n - 1][sum] != -1)
return tab[n - 1][sum];
// if the value of a[n-1] is
// greater than the sum.
// we call for the next value
if (a[n - 1] > sum)
return tab[n - 1][sum] = subsetSum(a, n - 1, sum);
else
{
// Here we do two calls because we
// don't know which value is
// full-fill our criteria
// that's why we doing two calls
return tab[n - 1][sum] = subsetSum(a, n - 1, sum) ||
subsetSum(a, n - 1, sum - a[n - 1]);
}
}
// Driver Code
int main()
{
// Storing the value -1 to the matrix
memset(tab, -1, sizeof(tab));
int n = 5;
int a[] = {1, 5, 3, 7, 4};
int sum = 12;
if (subsetSum(a, n, sum))
{
cout << "YES" << endl;
}
else
cout << "NO" << endl;
/* This Code is Contributed by Ankit Kumar*/
}
Java
// Java program for the above approach
class GFG {
// Check if possible subset with
// given sum is possible or not
static int subsetSum(int a[], int n, int sum)
{
// Storing the value -1 to the matrix
int tab[][] = new int[n + 1][sum + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
tab[i][j] = -1;
}
}
// If the sum is zero it means
// we got our expected sum
if (sum == 0)
return 1;
if (n <= 0)
return 0;
// If the value is not -1 it means it
// already call the function
// with the same value.
// it will save our from the repetition.
if (tab[n - 1][sum] != -1)
return tab[n - 1][sum];
// if the value of a[n-1] is
// greater than the sum.
// we call for the next value
if (a[n - 1] > sum)
return tab[n - 1][sum]
= subsetSum(a, n - 1, sum);
else {
// Here we do two calls because we
// don't know which value is
// full-fill our criteria
// that's why we doing two calls
if (subsetSum(a, n - 1, sum) != 0
|| subsetSum(a, n - 1, sum - a[n - 1])
!= 0) {
return tab[n - 1][sum] = 1;
}
else
return tab[n - 1][sum] = 0;
}
}
// Driver Code
public static void main(String[] args)
{
int n = 5;
int a[] = { 1, 5, 3, 7, 4 };
int sum = 12;
if (subsetSum(a, n, sum) != 0) {
System.out.println("YES\n");
}
else
System.out.println("NO\n");
}
}
// This code is contributed by rajsanghavi9.
Python3
# Python program for the above approach
# Taking the matrix as globally
tab = [[-1 for i in range(2000)] for j in range(2000)]
# Check if possible subset with
# given sum is possible or not
def subsetSum(a, n, sum):
# If the sum is zero it means
# we got our expected sum
if (sum == 0):
return 1
if (n <= 0):
return 0
# If the value is not -1 it means it
# already call the function
# with the same value.
# it will save our from the repetition.
if (tab[n - 1][sum] != -1):
return tab[n - 1][sum]
# if the value of a[n-1] is
# greater than the sum.
# we call for the next value
if (a[n - 1] > sum):
tab[n - 1][sum] = subsetSum(a, n - 1, sum)
return tab[n - 1][sum]
else:
# Here we do two calls because we
# don't know which value is
# full-fill our criteria
# that's why we doing two calls
tab[n - 1][sum] = subsetSum(a, n - 1, sum)
return tab[n - 1][sum] or subsetSum(a, n - 1, sum - a[n - 1])
# Driver Code
n = 5
a = [1, 5, 3, 7, 4]
sum = 12
if (subsetSum(a, n, sum)):
print("YES")
else:
print("NO")
# This code is contributed by shivani.
C#
// C# program for the above approach
using System;
class GFG
{
// Check if possible subset with
// given sum is possible or not
static int subsetSum(int []a, int n, int sum)
{
// Storing the value -1 to the matrix
int [,]tab = new int[n + 1,sum + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
tab[i,j] = -1;
}
}
// If the sum is zero it means
// we got our expected sum
if (sum == 0)
return 1;
if (n <= 0)
return 0;
// If the value is not -1 it means it
// already call the function
// with the same value.
// it will save our from the repetition.
if (tab[n - 1,sum] != -1)
return tab[n - 1,sum];
// if the value of a[n-1] is
// greater than the sum.
// we call for the next value
if (a[n - 1] > sum)
return tab[n - 1,sum]
= subsetSum(a, n - 1, sum);
else {
// Here we do two calls because we
// don't know which value is
// full-fill our criteria
// that's why we doing two calls
if (subsetSum(a, n - 1, sum) != 0
|| subsetSum(a, n - 1, sum - a[n - 1])
!= 0) {
return tab[n - 1,sum] = 1;
}
else
return tab[n - 1,sum] = 0;
}
}
// Driver Code
public static void Main(String[] args)
{
int n = 5;
int []a = { 1, 5, 3, 7, 4 };
int sum = 12;
if (subsetSum(a, n, sum) != 0) {
Console.Write("YES\n");
}
else
Console.Write("NO\n");
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript Program for the above approach
// Check if possible subset with
// given sum is possible or not
function subsetSum(a, n, sum) {
// If the sum is zero it means
// we got our expected sum
if (sum == 0)
return 1;
if (n <= 0)
return 0;
// If the value is not -1 it means it
// already call the function
// with the same value.
// it will save our from the repetition.
if (tab[n - 1][sum] != -1)
return tab[n - 1][sum];
// if the value of a[n-1] is
// greater than the sum.
// we call for the next value
if (a[n - 1] > sum)
return tab[n - 1][sum] = subsetSum(a, n - 1, sum);
else {
// Here we do two calls because we
// don't know which value is
// full-fill our criteria
// that's why we doing two calls
return tab[n - 1][sum] = subsetSum(a, n - 1, sum) ||
subsetSum(a, n - 1, sum - a[n - 1]);
}
}
// Driver Code
// Storing the value -1 to the matrix
let tab = Array(2000).fill().map(() => Array(2000).fill(-1));
let n = 5;
let a = [1, 5, 3, 7, 4];
let sum = 12;
if (subsetSum(a, n, sum)) {
document.write("YES" + "<br>");
}
else {
document.write("NO" + "<br>");
}
// This code is contributed by Potta Lokesh
</script>
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