序列是对象的集合，在我们的例子中，它是整数的集合。任务是判断元素内使用加减运算符的序列是否能被 m 整除。
问题陈述给定一个整数 m 和一个整数数组。仅使用元素之间的加法和减法检查是否存在其解可被 m 整除的有效序列。
示例 1input: m = 2, arr = {1, 2, 5}
output: true
解释 - 对于给定的数组，可能存在有效序列 {1 + 2 + 5} = {8}，且可被 2 整除。
示例 2input: m = 4, arr = {1, 2}
output: false
解释 - 对于给定的数组，不可能存在其解可被 4 整除的序列。
方法 1：暴力方法解决该问题的一个简单方法是使用递归函数查找数组的所有可能序列，然后检查是否有任何序列可被 m 整除。
伪代码procedure divisible (m, arr[], index, sum, n) if index == n if sum is a multiple of m ans = true end if ans = false end if divisible(m, arr, index + 1, sum + arr[index], n) or divisible(m, arr, index + 1, sum - arr[index], n)end procedure
示例：c++ 实现在下面的程序中，我们使用递归方法查找所有有效序列，然后检查是否有任何有效序列可被 m 整除。
#include <bits/stdc++.h>using namespace std;// recusive function to find if a valid sequence is divisible by m or notbool divisible(int m, int arr[], int index, int sum, int n){ // cheking the divisiblilty by m when the array ends if (index == n) { if (sum % m == 0){ return true; } return false; } // if either of addition or subtraction is true, return true return divisible(m, arr, index + 1, sum + arr[index], n) || divisible(m, arr, index + 1, sum - arr[index], n);}int main(){ int m = 4, arr[2] = {1, 5}; if (divisible(m, arr, 0, 0, 2)){ cout << true; } else{ cout << false; } return 0;}
输出true



时间复杂度 - o(2^n) 由于使用了递归。
空间复杂度 - o(n) 由于递归堆栈空间。
方法 2：回溯此方法类似于之前的强力递归方法，不同之处在于使用回溯，我们可以回溯搜索空间，以免走上我们知道不具有可被 m 整除的有效序列的路径。
伪代码procedure divisible (m, arr[], index, sum, n) if index == n if sum is a multiple of m ans = true end if ans = false end if if divisible(m, arr, index + 1, sum + arr[index], n) ans = true end if if divisible(m, arr, index + 1, sum - arr[index], n) ans = true end if ans = falseend procedure
示例：c++ 实现在下面的程序中，我们使用回溯来修剪搜索空间，以找到问题的解决方案。
#include <bits/stdc++.h>using namespace std;// function to find if a valid sequence is divisible by m or notbool divisible(int m, int arr[], int index, int sum, int n){ // cheking the divisiblilty by m when the array ends if (index == n){ if (sum % m == 0){ return true; } return false; } // checking the divisibility of sum + arr[index] if (divisible(m, arr, index + 1, sum + arr[index], n)){ return true; } // checking the divisibility of sum - arr[index] if (divisible(m, arr, index + 1, sum - arr[index], n)){ return true; } return false;}int main(){ int m = 4, arr[2] = {1, 5}; if (divisible(m, arr, 0, 0, 2)){ cout << true; } else{ cout << false; } return 0;}
输出true



时间复杂度 - 最坏情况下的时间复杂度为 o(2^n)，但实际上由于搜索空间的修剪，它比暴力方法更好。
空间复杂度 - 由于递归堆栈空间而导致的 o(n)。
方法 3：贪婪方法该问题的贪心解决方案是首先按升序对数组进行排序，然后在总和不超过 m 的情况下贪婪地应用加法函数。这种方法可能不会给出全局最优解，但会给出局部最优解。伪代码procedure divisible (m, arr[]) sum = 0 for i = 1 to end of arr sum = sum + arr[i] if sum is divisible by m ans = true end if sort array arr[] i = 0 j = last index of array while i < j if arr[j] - arr[i] is divisible by m ans = true end if if sum % m == (sum - arr[j]) % m sum = sum - arr[j] j = j - 1 else sum = sum - arr[i] i = i + 1 end if ans = falseend procedure
示例：c++ 实现在下面的程序中，对数组进行排序以找到可被 m 整除的最佳局部子数组。
#include <bits/stdc++.h>using namespace std;// greedy function to find if a valid sequence is divisible by m or notbool divisible(int m, vector<int> &arr){ int sum = 0; for (int i = 0; i < arr.size(); i++) { sum += arr[i]; } // checking if sumof all elements is divisible by m if (sum % m == 0){ return true; } sort(arr.begin(), arr.end()); int i = 0, j = arr.size() - 1; while (i < j){ // checking if the difference between the largest and smallest element at a time in the array is divisible by m if ((arr[j] - arr[i]) % m == 0){ return true; } // removing either the largest or smallest element based on which does not affect the sum's divisibility if (sum % m == (sum - arr[i]) % m){ sum -= arr[i]; i++; } else{ sum -= arr[j]; j--; } } return false;}int main(){ int m = 4; int array[2] = {1, 3}; vector<int> arr(array, array + 2); if (divisible(m, arr)){ cout << true; } else{ cout << false; } return 0;}
输出true



方法 4：动态规划使用动态规划的概念，在此解决方案中我们存储评估的中间结果。我们将创建一个包含 n+1 行和 m 列的表，并且当我们不使用数组元素时，结果 % m == 0 的基本情况。然后迭代模 m 的所有可能余数，我们更新表格。
伪代码procedure divisible (arr[], m , n) dp[n+1][m] = false dp[0][0] = true for i = 1 to n for i = j to m mod = arr[ i- 1] % m dp[i][j] = dp[i - 1][(j - mod + m) % m] or dp[i - 1][(j + mod) % m] ans = dp[n][0]end procedure
示例：c++ 实现在下面的程序中，我们将问题分解为子问题，然后解决它们。
#include <bits/stdc++.h>using namespace std;// function to find if a valid sequence is divisible by m or notbool divisible(int arr[], int m, int n){ // creating the dp table of size n+1 * m vector<vector<bool> > dp(n + 1, vector<bool>(m, false)); // base case dp[0][0] = true; // for each element iterating over all possible remainders j modulo m for (int i = 1; i <= n; i++){ for (int j = 0; j < m; j++){ int mod = arr[i - 1] % m; // either exclude or include the current element in the table dp[i][j] = dp[i - 1][(j - mod + m) % m] || dp[i - 1][(j + mod) % m]; } } return dp[n][0];}int main(){ int m = 4; int arr[2] = {1, 3}; if (divisible(arr, m, 2)){ cout << true; } else{ cout << false; } return 0;}
输出true



结论总而言之，为了找到可被 m 整除的有效序列，我们可以应用多种方法以及不同的关系和空间分析，范围从暴力情况下的 o(2^n) 到动态情况下的 o(nm)编程是最有效的方法。
以上就是检查是否有任何有效的序列可以被m整除的详细内容。