5852. Minimize the Difference Between Target and Chosen Elements

Description

image-20210822232736812

image-20210822232747878

image-20210822232755203

Solution

DFS + memorize visited + pruning

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    vector<vector<int>> visited;
    int res = INT_MAX;
public:
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        int m = mat.size(), n = mat[0].size();
        for(int i = 0; i < m; i++)
            sort(mat[i].begin(), mat[i].end());
        visited.resize(m, vector<int>(4901,0));
        stack<pair<int, int>> stk;
        stk.push({0,0});
        while(!stk.empty()){
            auto [level, sum] = stk.top();
            stk.pop();
            if(level == mat.size()){
                res = min(res, abs(sum - target));
                continue;
            }
            for(int i = 0; i < mat[0].size();i++){
                if(visited[level][sum + mat[level][i]])
                    continue;
                visited[level][sum + mat[level][i]] = 1;
                stk.push({level+1, sum + mat[level][i]});
                //important pruning situation
                if(sum + mat[level][i] > target)
                    break;
            }
        }
        return res;
    }
    
};

image-20210822233549504