C++ DFS/backtracking/pruning using DP, 32ms


  • 0
    F
    class Solution {
    public:
        vector<int> _maxSubset;
        int _n;
        // idx to start with    maxPrefix[idx] : maximum size of all subsets from [0:idx]
        void dfs(const vector<int> &nums, int idx, vector<int> &maxPrefix, vector<int> &subset)
        {
            // i < idx have been processed
            if(idx == _n) return;
            if(_maxSubset.size() - subset.size() > (_n-idx)) return;
            bool divisible = true;
            for(const auto &v : subset) {
                if(nums[idx] % v != 0) {
                    divisible = false;
                    break;
                }
            }
            if(divisible && (int(subset.size()) >= (maxPrefix[idx]-1))) {
                subset.push_back(nums[idx]);
                maxPrefix[idx] = max(maxPrefix[idx], int(subset.size()));
                if(subset.size() > _maxSubset.size()) {
                    _maxSubset = subset;
                }
                dfs(nums, idx+1, maxPrefix, subset);
                subset.pop_back();
            }
            if(int(subset.size()) >= (maxPrefix[idx]-1)) {
                dfs(nums, idx+1, maxPrefix, subset);
                maxPrefix[idx] = max(maxPrefix[idx], int(subset.size()));
            }
    
        }
    
        vector<int> largestDivisibleSubset(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            _n = nums.size();
            vector<int> maxPrefix(nums.size(), 0);
            vector<int> subset;
            dfs(nums, 0, maxPrefix, subset);
            return _maxSubset;
        }
    };

Log in to reply
 

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