序列是物件的集合，在我們的例子中，它是整數的集合。任務是判斷元素內使用加減運算子的序列是否能被 M 整除。
給定一個整數 M 和一個整數陣列。僅使用元素之間的加法和減法檢查是否存在其解可被 M 整除的有效序列。
Input: M = 2, arr = {1, 2, 5}
Output: TRUE
解釋- 對於給定的數組，可能存在有效序列 {1 2 5} = {8}，且可被 2 整除。
Input: M = 4, arr = {1, 2}
Output: FALSE
解釋- 對於給定的數組，不可能存在其解可被 4 整除的序列。
解決這個問題的簡單方法是使用遞歸函數來尋找陣列的所有可能序列，然後檢查是否有任何序列可被 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
在下面的程式中，我們使用遞歸方法來尋找所有有效序列，然後檢查是否有任何有效序列可被 M 整除。
#includeusing namespace std; // Recusive function to find if a valid sequence is divisible by M or not bool 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) 由於遞歸堆疊空間。
此方法類似於先前的強力遞歸方法，不同之處在於使用回溯，我們可以回溯搜尋空間，以免走上我們知道不具有可被 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 = false end procedure
在下面的程式中，我們使用回溯來修剪搜尋空間，以找到問題的解決方案。
#includeusing namespace std; // Function to find if a valid sequence is divisible by M or not bool 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)。
這個問題的貪心解法是先將陣列依升序排序，然後在總和不超過 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 = false end procedure
在下面的程式中，將陣列進行排序以找到可被 M 整除的最佳局部子陣列。
#includeusing namespace std; // Greedy function to find if a valid sequence is divisible by M or not bool divisible(int M, vector &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 arr(array, array + 2); if (divisible(M, arr)){ cout << "TRUE"; } else{ cout << " FALSE"; } return 0; }
TRUE
使用動態規劃的概念，在此解決方案中我們儲存評估的中間結果。我們將建立一個包含 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
在下面的程式中，我們將問題分解為子問題，然後解決它們。
