Verifique si es posible obtener una suma dada de un conjunto dado de elementos

Dada una array de números y un entero x. Encuentre si es posible o no obtener x agregando elementos de una array dada, podemos elegir un solo elemento varias veces. Para una array dada, puede haber muchas consultas de suma.
Ejemplos: 
 

Input : arr[] = { 2, 3}
         q[]  = {8, 7}
Output : Yes Yes
Explanation : 
2 + 2 + 2 + 2 = 8
2 + 2 + 3 = 7

La idea es ordenar primero la array dada y luego usar el concepto similar a Sieve of Eratosthenes . Primero tome una array de gran tamaño (que es el tamaño máximo de x). Inicialmente mantenga cero en todos sus índices. Haga 1 en el índice cero (podemos obtener cero cualquiera que sea la array). Ahora, recorra toda la array y haga que todos los valores posibles sean 1.
 

// CPP program to find if we can get given
// sum using elements of given array.
#include <bits/stdc++.h>
using namespace std;
 
// maximum size of x
const int MAX = 1000;
 
// to check whether x is possible or not
int ispossible[MAX];
 
void check(int arr[], int N)
{
    ispossible[0] = 1;
    sort(arr, arr + N);
 
    for (int i = 0; i < N; ++i) {
        int val = arr[i];
 
        // if it is already possible
        if (ispossible[val])
            continue;
 
        // make 1 to all it's next elements
        for (int j = 0; j + val < MAX; ++j)
            if (ispossible[j])
                ispossible[j + val] = 1;
    }
}
 
// Driver code
int main()
{
    int arr[] = { 2, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
    check(arr, N);
    int x = 7;
    if (ispossible[x])
        cout << x << " is possible.";
    else
        cout << x << " is not possible.";
    return 0;
}

// C program to find if we can get given
// sum using elements of given array.
#include <stdio.h>
 
// maximum size of x
#define MAX 1000
 
// to check whether x is possible or not
int ispossible[MAX];
 
void check(int arr[], int N)
{
    ispossible[0] = 1;
    int temp;
    for (int i = 0; i < N; i++) {    
        for (int j = i+1; j < N; j++) {    
           if(arr[i] > arr[j]) {   
               temp = arr[i];   
               arr[i] = arr[j];   
               arr[j] = temp;   
           }    
        }    
    }   
    for (int i = 0; i < N; ++i) {
        int val = arr[i];
 
        // if it is already possible
        if (ispossible[val])
            continue;
 
        // make 1 to all it's next elements
        for (int j = 0; j + val < MAX; ++j)
            if (ispossible[j])
                ispossible[j + val] = 1;
    }
}
 
// Driver code
int main()
{
    int arr[] = { 2, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
    check(arr, N);
    int x = 7;
    if (ispossible[x])
        printf("%d is possible.",x);
    else
        printf("%d is not possible.",x);
    return 0;
}
 
// This code is contributed by kothavvsaakash.

// Java program to find if we can get given
// sum using elements of given array.
import java.util.*;
 
class solution
{
 
// maximum size of x
int MAX = 1000;
 
// to check whether x is possible or not
static int []ispossible = new int[1000];
static void check(int[] arr, int N)
{
     
    ispossible[0] = 1;
    Arrays.sort(arr);
 
    for (int i = 0; i < N; ++i) {
        int val = arr[i];
 
        // if it is already possible
        if (ispossible[val] == 1)
            continue;
 
        // make 1 to all it's next elements
        for (int j = 0; j + val < 1000; ++j)
            if (ispossible[j]== 1)
                ispossible[j + val] = 1;
    }
}
 
// Driver code
public static void main(String args[])
{
    int[] arr = { 2, 3 };
    int N = arr.length;
    check(arr, N);
    int x = 7;
    if (ispossible[x]== 1)
        System.out.println(x+" is possible.");
    else
        System.out.println(x+" is not possible.");
 
}
}
// This code is contributed by
// Shashank_Sharma

# Python3 program to find if we can get given
# sum using elements of the given array.
def check(arr, N):
 
    ispossible[0] = 1
    arr.sort()
 
    for i in range(0, N):
        val = arr[i]
 
        # if it is already possible
        if ispossible[val]:
            continue
 
        # make 1 to all it's next elements
        for j in range(0, MAX - val):
            if ispossible[j]:
                ispossible[j + val] = 1
 
# Driver code
if __name__ == "__main__":
 
    arr = [2, 3]
    N = len(arr)
     
    # maximum size of x
    MAX = 1000
     
    # to check whether x is possible or not
    ispossible = [0] * MAX
 
    check(arr, N)
    x = 7
     
    if ispossible[x]:
        print(x, "is possible.")
    else:
        print(x, "is not possible.")
     
# This code is contributed by
# Rituraj Jain

// C# program to find if we can get given
// sum using elements of given array.
using System;
 
class GFG
{
     
// to check whether x is possible or not
static int []ispossible = new int[1000];
static void check(int[] arr, int N)
{
     
    ispossible[0] = 1;
    Array.Sort(arr);
 
    for (int i = 0; i < N; ++i)
    {
        int val = arr[i];
 
        // if it is already possible
        if (ispossible[val] == 1)
            continue;
 
        // make 1 to all it's next elements
        for (int j = 0; j + val < 1000; ++j)
            if (ispossible[j] == 1)
                ispossible[j + val] = 1;
    }
}
 
// Driver code
public static void Main()
{
    int[] arr = { 2, 3 };
    int N = arr.Length;
    check(arr, N);
    int x = 7;
    if (ispossible[x]== 1)
        Console.WriteLine(x + " is possible.");
    else
        Console.WriteLine(x + " is not possible.");
}
}
 
// This code is contributed by
// Akanksha Rai

<?php
// PHP program to find if we can get given
// sum using elements of given array.
 
// maximum size of x
$MAX = 1000;
 
// to check whether x is possible or not
$ispossible[$MAX] = array();
 
function check($arr, $N)
{
    global $MAX;
    $ispossible[0] = 1;
    sort($arr, 0);
 
    for ($i = 0; $i < $N; ++$i)
    {
        $val = $arr[$i];
 
        // if it is already possible
        if ($ispossible[$val])
            continue;
 
        // make 1 to all it's next elements
        for ($j = 0; $j + $val < $MAX; ++$j)
            if ($ispossible[$j])
                $ispossible[$j + $val] = 1;
    }
}
 
// Driver code
$arr = array( 2, 3 );
$N = sizeof($arr);
check($arr, $N);
$x = 7;
if (ispossible[$x])
    echo $x . " is possible.";
else
    echo $x . " is not possible.";
 
// This code is contributed
// by Akanksha Rai
?>

<script>
// Javascript program to find if we can get given
// sum using elements of given array.
 
// maximum size of x
let MAX = 1000;
 
// to check whether x is possible or not
let ispossible = new Array(MAX);
 
function check(arr, N)
{
    ispossible[0] = 1;
    arr.sort();
 
    for (let i = 0; i < N; ++i)
    {
        val = arr[i];
 
        // if it is already possible
        if (ispossible[val])
            continue;
 
        // make 1 to all it's next elements
        for (let j = 0; j + val < MAX; ++j)
            if (ispossible[j])
                ispossible[j + val] = 1;
    }
}
 
// Driver code
let arr = new Array( 2, 3 );
let N = arr.length;
check(arr, N);
let x = 7;
if (ispossible[x])
    document.write(x + " is possible.");
else
    document.write(x + " is not possible.");
 
// This code is contributed
// by _sauraahb_jaiswal
</script>

Producción: 
 

7 is possible.