问题陈述 - 我们给出了一个包含 n 个整数的数组。此外，我们还给出了表示二进制字符串长度的整数 m。我们需要创建一个长度为 m 的二进制字符串，使其遵循以下条件。
如果我们能从数组中找到总和等于索引“i”的子集，则索引“i”处的字符为 1；否则为 0。
我从1开始的索引。
示例示例input – arr = [1, 2] m = 4
output – 1110
说明总和等于 1 的子集是 {1}。
总和等于 2 的子集是 {2}。
总和等于 3 的子集是 {1, 2}。
我们找不到总和等于 4 的子集，因此我们将 0 放在第 4 个索引处。
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”变量并使用空字符串对其进行初始化。
第二步 - 使用for循环使总迭代次数等于字符串长度。
第三步 - 在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到sum进行迭代。
步骤 5.5 - 在 for 循环中，如果当前元素的值大于总和，则忽略它。
步骤 5.6 − 否则，包括或排除元素以获得总和。
步骤 5.7 − 返回包含结果的 ‘dptable[n][sum]’。
示例#include <iostream>#include <vector>using namespace std;// function to check if subset-sum is possiblebool 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()函数中使用了一个二维向量。
使用bitset的方法在这种方法中，我们将使用位集通过组合数组的不同元素来查找所有可能的总和值。这里，bitset 意味着它创建一个二进制字符串。在结果位集中，它的每一位都代表总和是否可能等于特定索引，我们需要在这里找到它。
算法第 1 步 - 定义数组和 m。此外，定义 createbinarystring() 函数。
第 2 步 - 接下来，定义所需长度的位集，这将创建一个二进制字符串。
第三步 - 将bit[0]初始化为1，因为总和为0总是可能的。
第 4 步 - 使用 for 循环迭代数组元素
。步骤 5 - 首先，对数组元素执行“bit”左移操作。然后将结果值与位值进行或运算。
步骤 6 − 从索引 1 到 m 打印位集的值。
示例#include <bits/stdc++.h>using namespace std;// function to construct the binary stringvoid 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)，因为我们存储了位集的值。
结论在这里，我们优化了第二种方法，从空间和时间复杂度来看，它比第一种方法更好。然而，如果你没有对位集的了解，第二种方法可能对初学者来说很难理解。
以上就是根据给定条件，从数组中构建一个长度为k的二进制字符串的详细内容。