Memoization for Backtracking

Most backtracking involves some repeated searching; a memo can record earlier search results so you can return directly when you reach the same node

idx is an important index: to its left are idx + 1 ~ n-1 (i = idx + 1, idx + 2 … n-1)

Likewise, the values of i in the subtree of idx are also idx + 1 ~ n-1 (i = idx + 1, idx + 2 … n-1)

• Therefore, using idx and the depth as the memo key is a good way to store this node

Example

link : https://leetcode.com/problems/combinations/description/

class Solution {
public:
     vector<vector<int>> memo[21][21];
    vector<vector<int>> combine(int n, int k, int cur=1) {
        if(k == 0) return {{}};
       
        if(!memo[k][cur].empty()) {
           cout << k << "memo"<<cur;
            return memo[k][cur];
            }
        
        vector<vector<int>> ans;
        for(int i=cur; i<=n; i++){
            cout << "before idx= "<< cur <<" before i=" <<i+1 << " k = "<<k-1<< " ;";
            vector<vector<int>> temp = combine(n, k-1, i+1);
            for(auto v: temp){
                v.push_back(i);
                ans.push_back(v);
            }
            cout << endl;
            cout << "back idx= "<< cur <<" back i="<<i<< " k = "<<k<< endl;
        }
        cout << "end" << endl;
        cout << endl;
        for (auto a:ans){
            cout << "[";
            for (auto b:a) {
                cout << b<<" ";
            }
             cout << "]";
        }
        cout << endl;

        cout << "k=" << k << " idx = " << cur << endl;
        // cout << cur << endl;
        return memo[k][cur] = ans;
    }
};

out :

before idx= 1 before i=2 k = 2 ;before idx= 2 before i=3 k = 1 ;before idx= 3 before i=4 k = 0 ;
back idx= 3 back i=3 k = 1
before idx= 3 before i=5 k = 0 ;
back idx= 3 back i=4 k = 1
before idx= 3 before i=6 k = 0 ;
back idx= 3 back i=5 k = 1
end

[3 ][4 ][5 ]
k=1 idx = 3

back idx= 2 back i=2 k = 2
before idx= 2 before i=4 k = 1 ;before idx= 4 before i=5 k = 0 ;
back idx= 4 back i=4 k = 1
before idx= 4 before i=6 k = 0 ;
back idx= 4 back i=5 k = 1
end

[4 ][5 ]
k=1 idx = 4

back idx= 2 back i=3 k = 2
before idx= 2 before i=5 k = 1 ;before idx= 5 before i=6 k = 0 ;
back idx= 5 back i=5 k = 1
end

[5 ]
k=1 idx = 5

back idx= 2 back i=4 k = 2
before idx= 2 before i=6 k = 1 ;end


k=1 idx = 6

back idx= 2 back i=5 k = 2
end

[3 2 ][4 2 ][5 2 ][4 3 ][5 3 ][5 4 ]
k=2 idx = 2

back idx= 1 back i=1 k = 3
before idx= 1 before i=3 k = 2 ;before idx= 3 before i=4 k = 1 ;1memo4
back idx= 3 back i=3 k = 2
before idx= 3 before i=5 k = 1 ;1memo5
back idx= 3 back i=4 k = 2
before idx= 3 before i=6 k = 1 ;end


k=1 idx = 6

back idx= 3 back i=5 k = 2
end

[4 3 ][5 3 ][5 4 ]
k=2 idx = 3

back idx= 1 back i=2 k = 3
before idx= 1 before i=4 k = 2 ;before idx= 4 before i=5 k = 1 ;1memo5
back idx= 4 back i=4 k = 2
before idx= 4 before i=6 k = 1 ;end


k=1 idx = 6

back idx= 4 back i=5 k = 2
end

[5 4 ]
k=2 idx = 4

back idx= 1 back i=3 k = 3
before idx= 1 before i=5 k = 2 ;before idx= 5 before i=6 k = 1 ;end


k=1 idx = 6

back idx= 5 back i=5 k = 2
end


k=2 idx = 5

back idx= 1 back i=4 k = 3
before idx= 1 before i=6 k = 2 ;end


k=2 idx = 6

back idx= 1 back i=5 k = 3
end

[3 2 1 ][4 2 1 ][5 2 1 ][4 3 1 ][5 3 1 ][5 4 1 ][4 3 2 ][5 3 2 ][5 4 2 ][5 4 3 ]
k=3 idx = 1