Construya una string binaria de longitud K a partir de una array basada en condiciones dadas

Dada una array arr[] que consta de N enteros y un entero K , la tarea es construir una string binaria de longitud K que satisfaga las siguientes condiciones: 
 

1. El carácter en el i ^-ésimo índice es ‘ 1′ si se puede formar un subconjunto con suma i a partir de la array.
2. De lo contrario, el carácter en el i ^-ésimo índice es ‘0’ .

Ejemplos:

Entrada: arr[] = {1, 4}, K = 5
Salida: 10011
Explicación: 
El carácter en el primer índice se puede formar con ‘1’ considerando el subconjunto {1}. 
El carácter en el cuarto índice se puede hacer con ‘1’ considerando el subconjunto {4}. 
El carácter en el quinto índice se puede hacer con ‘1’ considerando el subconjunto {1, 4}.

Entrada: arr[] = {1, 6, 1}, K = 8
Salida: 11000111

Enfoque: La idea es utilizar un enfoque codicioso para resolver este problema. A continuación se muestran los pasos:

• Inicialice un conjunto de bits , digamos bit[] , de tamaño 10 ⁵ + 5 y establezca bit[0] = 1.
• Atraviese el arreglo y para cada elemento del arreglo arr[i] , actualice bit como bit |= bit << arr[i] p p
• i ^-ésima iteración << arr[i] p p + arr[i].
• | (bit << arr[i])
• Iterar de 1 a K e imprimir cada bit de valor [i] como la string binaria requerida.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// To construct the
// required binary string
bitset<100003> bit;
 
// Function to construct binary string
// according to the given conditions
void constructBinaryString(int arr[],
                           int N, int K)
{
    // Initialize with 1
    bit[0] = 1;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // To check if the i-th integer
        // needs to be considered or not
        bit |= bit << arr[i];
    }
 
    // Print the binary string
    for (int i = 1; i <= K; i++) {
        cout << bit[i];
    }
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 1, 6, 1 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Given K
    int K = 8;
 
    constructBinaryString(arr, N, K);
}

# Python program for the above approach
 
# To construct the
# required binary string
#bit = [0]*100003
 
# Function to construct binary string
# according to the given conditions
def constructBinaryString(arr,N, K):
     
    # Initialize with 1
    bit = 1
     
    # Traverse the array
    for i in range(0, N):
       
        # To check if the i-th eger
        # needs to be considered or not
        bit |= bit << arr[i]
     
    # Print the binary string
    #for i in range(1,K):
    #    print(bit[i])
    bit = bin(bit).replace("0b", "")
    print(bit[1:K + 1])
     
# Driver Code
# Given array
arr = [1, 6, 1]
 
# Size of the array
N = len(arr)
 
# Given K
K = 8
 
constructBinaryString(arr, N, K)
 
# This code is contributed by shubhamsingh10

11000111

Complejidad temporal: O(N)
Espacio auxiliar: O(N)