3548. Equal Sum Grid Partition II Hard

1/**
2 * [3548] Equal Sum Grid Partition II
3 *
4 * You are given an m x n matrix grid of positive integers. Your task is to determine if it is possible to make either one horizontal or one vertical cut on the grid such that:
5 * 
6 * 	Each of the two resulting sections formed by the cut is non-empty.
7 * 	The sum of elements in both sections is equal, or can be made equal by discounting at most one single cell in total (from either section).
8 * 	If a cell is discounted, the rest of the section must remain connected.
9 * 
10 * Return true if such a partition exists; otherwise, return false.
11 * Note: A section is connected if every cell in it can be reached from any other cell by moving up, down, left, or right through other cells in the section.
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">grid = [[1,4],[2,3]]</span>
16 * Output: <span class="example-io">true</span>
17 * Explanation:
18 * <img alt="" src="https://assets.leetcode.com/uploads/2025/03/30/lc.jpeg" style="height: 180px; width: 180px;" />
19 * 
20 * 	A horizontal cut after the first row gives sums 1 + 4 = 5 and 2 + 3 = 5, which are equal. Thus, the answer is true.
21 * </div>
22 * <strong class="example">Example 2:
23 * <div class="example-block">
24 * Input: <span class="example-io">grid = [[1,2],[3,4]]</span>
25 * Output: <span class="example-io">true</span>
26 * Explanation:
27 * <img alt="" src="https://assets.leetcode.com/uploads/2025/04/01/chatgpt-image-apr-1-2025-at-05_28_12-pm.png" style="height: 180px; width: 180px;" />
28 * 
29 * 	A vertical cut after the first column gives sums 1 + 3 = 4 and 2 + 4 = 6.
30 * 	By discounting 2 from the right section (6 - 2 = 4), both sections have equal sums and remain connected. Thus, the answer is true.
31 * </div>
32 * <strong class="example">Example 3:
33 * <div class="example-block">
34 * Input: <span class="example-io">grid = [[1,2,4],[2,3,5]]</span>
35 * Output: <span class="example-io">false</span>
36 * Explanation:
37 * <img alt="" src="https://assets.leetcode.com/uploads/2025/04/01/chatgpt-image-apr-2-2025-at-02_50_29-am.png" style="height: 180px; width: 180px;" />
38 * 
39 * 	A horizontal cut after the first row gives 1 + 2 + 4 = 7 and 2 + 3 + 5 = 10.
40 * 	By discounting 3 from the bottom section (10 - 3 = 7), both sections have equal sums, but they do not remain connected as it splits the bottom section into two parts ([2] and [5]). Thus, the answer is false.
41 * </div>
42 * <strong class="example">Example 4:
43 * <div class="example-block">
44 * Input: <span class="example-io">grid = [[4,1,8],[3,2,6]]</span>
45 * Output: <span class="example-io">false</span>
46 * Explanation:
47 * No valid cut exists, so the answer is false.
48 * </div>
49 *  
50 * Constraints:
51 * 
52 * 	1 <= m == grid.length <= 10^5
53 * 	1 <= n == grid[i].length <= 10^5
54 * 	2 <= m * n <= 10^5
55 * 	1 <= grid[i][j] <= 10^5
56 * 
57 */
58pub struct Solution {}
59
60// problem: https://leetcode.com/problems/equal-sum-grid-partition-ii/
61// discuss: https://leetcode.com/problems/equal-sum-grid-partition-ii/discuss/?currentPage=1&orderBy=most_votes&query=
62
63// submission codes start here
64
65impl Solution {
66    pub fn can_partition_grid(grid: Vec<Vec<i32>>) -> bool {
67        false
68    }
69}
70
71// submission codes end
72
73#[cfg(test)]
74mod tests {
75    use super::*;
76
77    #[test]
78    fn test_3548() {
79    }
80}
81