基于给定条件从数组构造一个长度为 K 的二进制字符串

---

在本教程中，我们需要构造一个长度为 K 的二进制字符串，如果使用数组元素可以得到等于 I 的子集和，则它应该在第 i 个索引处包含“1”。我们将学习两种解决问题的方法。在第一种方法中，我们将使用动态规划方法来检查是否可以得到等于索引“I”的子集和。在第二种方法中，我们将使用位集查找使用数组元素的所有可能的和。

问题陈述 - 我们给定一个包含 N 个整数的数组。此外，我们还给定一个整数 M 表示二进制字符串的长度。我们需要创建一个长度为 M 的二进制字符串，使其满足以下条件。

• 如果我们可以在数组中找到一个和等于索引“I”的子集，则索引“I”处的字符为 1；否则为 0。

• 索引 I 从 1 开始。

示例

Input –  arr = [1, 2] M = 4

Output – 1110

解释

• 和等于 1 的子集是 {1}。

• 和等于 2 的子集是 {2}。

• 和等于 3 的子集是 {1, 2}。

• 我们找不到和等于 4 的子集，因此我们在第 4 个索引处放置了 0。

Input –  arr = [1, 3, 1] M = 9

Output – 111110000

解释

我们可以创建所有可能的组合以获得 1 到 5 之间的和。因此，前 5 个字符是 1，最后 4 个字符是 0。

Input –  arr = [2, 6, 3] M = 6

Output – 011011

解释

使用数组元素无法得到等于 1 和 4 的和，因此我们在第一个和第四个索引处放置了 0。

方法 1

在这种方法中，我们将使用动态规划来检查是否可以使用数组元素构造等于索引“I”的和。我们将对每个索引进行检查，并将 1 或 0 附加到二进制字符串。

算法

• 步骤 1 - 创建一个大小为 N 的向量，并将其初始化为整数值。此外，定义字符串类型的“bin”变量，并将其初始化为空字符串。

• 步骤 2 - 使用 for 循环进行总共 M 次迭代，等于字符串长度。

• 步骤 3 - 在 for 循环中，通过传递数组、N 和索引值作为参数来调用 isSubsetSum() 函数。

• 步骤 4 - 如果 isSubsetSum() 函数返回 true，则将“1”附加到“bin”。否则，将“0”附加到“bin”。

• 步骤 5 - 定义 isSubsetSum() 函数以检查是否可以使用数组元素得到和。

• 步骤 5.1 - 定义一个名为 dpTable 的二维向量。

• 步骤 5.2 - 将“dpTable[i][0]”初始化为 true，因为和为零总是可能的。这里，“I”是索引值。

• 步骤 5.3 - 将“dpTable[0][j]”初始化为 false，因为对于空数组来说和是不可能的。

• 步骤 5.4 - 现在，使用两个嵌套循环。第一个循环从 1 到 N 进行迭代，另一个从 1 到和进行迭代。

• 步骤 5.5 - 在 for 循环中，如果当前元素的值大于和，则忽略它。

• 步骤 5.6 - 否则，包含或排除元素以得到和。

• 步骤 5.7 - 返回包含结果的“dpTable[N][sum]”。

示例

#include <iostream>
#include <vector>
using namespace std;
// Function to check if subset-sum is possible
bool isSubsetSum(vector<int> &arr, int N, int sum){
   vector<vector<bool>> dpTable(N + 1, vector<bool>(sum + 1, false));
   
   // Base cases
   for (int i = 0; i <= N; i++)
   
      // If the sum is zero, then the answer is true
      dpTable[i][0] = true;
      
   // for an empty array, the sum is not possible
   for (int j = 1; j <= sum; j++)
      dpTable[0][j] = false;
      
   // Fill the dp table
   for (int i = 1; i <= N; i++){
      for (int j = 1; j <= sum; j++){
      
         // if the current element is greater than the sum, then we can't include it
         if (arr[i - 1] > j)
            dpTable[i][j] = dpTable[i - 1][j];
            
         // else we can either include it or exclude it to get the sum
         else
            dpTable[i][j] = dpTable[i - 1][j] || dpTable[i - 1][j - arr[i - 1]];
      }
   }
   
   // The last cell of the dp table contains the result
   return dpTable[N][sum];
}
int main(){

   // Given M
   int M = 9;
   
   // Creating the vector
   vector<int> arr = {1, 3, 1};
   
   // getting the size of the vector
   int N = arr.size();
   
   // Initializing the string
   string bin = "";
   
   // Making k iteration to construct the string of length k
   for (int i = 1; i <= M; i++){
   
      // if the subset sum is possible, then add 1 to the string, else add 0
      if (isSubsetSum(arr, N, i)){
         bin += "1";
      }
      else{
         bin += "0";
      }
   }
   
   // print the result.
   cout << "The constructed binary string of length " << M << " according to the given conditions is ";
   cout << bin;
   return 0;
}

输出

The constructed binary string of length 9 according to the given conditions is 111110000

时间复杂度 - O(N^3)，因为 isSubsetSum() 的时间复杂度为 O(N^2)，并且我们从驱动程序代码中调用了 N 次。

空间复杂度 - O(N^2)，因为我们在 isSubsetSum() 函数中使用了一个二维向量。

方法 2：使用位集

在这种方法中，我们将使用位集查找通过组合数组的不同元素的所有可能的和值。这里，位集表示它创建一个二进制字符串。在结果位集中，它的每个位都表示是否可以得到等于特定索引的和，这正是我们需要在这里找到的。

算法

• 步骤 1 - 定义数组和 M。此外，定义 createBinaryString() 函数。

• 步骤 2 - 接下来，定义所需长度的位集，它创建一个二进制字符串。

• 步骤 3 - 将 bit[0] 初始化为 1，因为和为 0 总是可能的。

• 步骤 4 - 使用 for 循环遍历数组元素

.

• 步骤 5 - 首先，对“bit”执行左移运算，并使用数组元素作为移位位数。之后，执行结果值和“bit”值的“或”运算。

• 步骤 6 - 打印从索引 1 到 M 开始的位集值。

示例

#include <bits/stdc++.h>
using namespace std;
// function to construct the binary string
void createBinaryString(int array[], int N, int M){
   bitset<100003> bit;
   
   // Initialize with 1
   bit[0] = 1;
   
   // iterate over all the integers
   for (int i = 0; i < N; i++){
      // perform left shift by array[i], and OR with the previous value.
      bit = bit | bit << array[i];
   }
   
   // Print the binary string
   cout << "The constructed binary string of length " << M << " according to the given conditions is ";
   for (int i = 1; i <= M; i++){
      cout << bit[i];
   }
}
int main(){

   // array of integers
   int array[] = {1, 4, 2};
   int N = sizeof(array) / sizeof(array[0]);
   
   // value of M, size of the string
   int M = 8;
   createBinaryString(array, N, M);
}

输出

The constructed binary string of length 8 according to the given conditions is 11111110

时间复杂度 - O(N)，因为我们使用单个 for 循环。

空间复杂度 - O(N)，因为我们存储位集值。

结论

在这里，我们优化了第二种方法，它在空间和时间复杂度方面都优于第一种方法。但是，如果您不了解位集，则第二种方法对于初学者来说可能难以理解。