Two Color Array Partitioning: Dynamic Programming Solution in C++

{"title":"You are given an array consisting of n\n integers. Your task is to determine whether it is possible to color all its elements in two colors in such a way that the sums of the elements of both colors have the same parity and each color has at least one element colored.\n\nFor example, if the array is [1,2,4,3,2,3,5,4\n], we can color it as follows: [1,2,4,3,2,3,5,4\n], where the sum of the blue elements is 6\n and the sum of the red elements is 18\n.c++代码内容：cpp\n#include <iostream>\n#include <vector>\n\nbool isPossibleToColor(const std::vector<int>& arr) {\n int sum = 0;\n for (int num : arr) {\n sum += num;\n }\n\n if (sum % 2 != 0) {\n return false;\n }\n\n int n = arr.size();\n std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(sum / 2 + 1, false));\n dp[0][0] = true;\n\n for (int i = 1; i <= n; i++) {\n for (int j = 0; j <= sum / 2; j++) {\n dp[i][j] = dp[i - 1][j];\n if (j >= arr[i - 1]) {\n dp[i][j] = dp[i][j] || dp[i - 1][j - arr[i - 1]];\n }\n }\n }\n\n return dp[n][sum / 2];\n}\n\nint main() {\n std::vector<int> arr = {1, 2, 4, 3, 2, 3, 5, 4};\n if (isPossibleToColor(arr)) {\n std::cout << "It is possible to color the array in two colors." << std::endl;\n } else {\n std::cout << "It is not possible to color the array in two colors." << std::endl;\n }\n\n return 0;\n}\n\nThe given problem can be solved using dynamic programming. We need to check if it is possible to partition the array into two subsets such that the sum of elements in each subset is equal and each subset has at least one element colored.\n\nThe isPossibleToColor function takes an array arr as input and returns a boolean value indicating whether it is possible to color the array in two colors as per the given conditions.\n\nFirst, we calculate the sum of all elements in the array. If the sum is odd, it is not possible to partition the array into two subsets with equal sums, so we return false.\n\nNext, we initialize a 2D boolean array dp of size (n+1) x (sum/2+1), where n is the size of the array and sum is the sum of all elements in the array.\n\nThe value dp[i][j] represents whether it is possible to form a subset of the first i elements of the array such that the sum of elements in the subset is j.\n\nWe initialize dp[0][0] as true, since it is always possible to form an empty subset with sum 0.\n\nThen, for each element in the array, we iterate over all possible sums from 0 to sum/2 and update the dp array based on the following conditions:\n- dp[i][j] is true if dp[i-1][j] is true, i.e., it is possible to form a subset of the first i-1 elements with sum j.\n- dp[i][j] is also true if j is greater than or equal to the current element arr[i-1] and dp[i-1][j-arr[i-1]] is true, i.e., it is possible to form a subset of the first i-1 elements with sum j-arr[i-1].\n\nAfter filling the dp array, we return the value of dp[n][sum/2], which indicates whether it is possible to form a subset of all elements with sum sum/2.\n\nIn the main function, we create an example array and check if it is possible to color the array in two colors using the isPossibleToColor function. We print the appropriate message based on the result.