C++ backtracking with caching


  • 0
    Y
    class Solution {
    public:
        vector<vector<int>> getFactors(int n) {
            unordered_map<int, vector<vector<int>>> cache;
            return backtrack(n, 2, true, cache);
        }
        
        vector<vector<int>> backtrack(int cur, int last, bool first, unordered_map<int, vector<vector<int>>> &cache) {
            if (cache.find(cur) != cache.end()) return cache[cur];
            
            vector<vector<int>> res;
            for (int i = last; i * i <= cur; i++) {
                if (cur % i == 0) {
                    vector<vector<int>> tmp = backtrack(cur / i, i, false, cache);
                    for (int j = 0; j < tmp.size(); j++) {
                        if (tmp[j][0] >= i) { // keep the numbers in non-decreasing order to avoid duplicates
                            tmp[j].insert(tmp[j].begin(), i);
                            res.push_back(tmp[j]);
                        }
                    }
                }
            }
            
            if (!first) res.push_back({cur}); // if not the first number, we can have cur = 1 * cur
            
            cache[cur] = res;
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.