С++ Passed Backtracking Solution with memoization


  • 1
    Z

    '''

    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 != 0)
            return false;
        
        unordered_set<int> bad_sum;
        return backTrack(nums, bad_sum, 0, sum / 2);
    }
    
    bool backTrack(vector<int>& nums, unordered_set<int>& bad_sum, int start, int sum) {
        if (sum <= 0)
            return sum == 0;
        
        if (bad_sum.find(sum) != bad_sum.end())
            return false;
            
        for (int i = start; i < nums.size(); i++) {
            if (backTrack(nums, bad_sum, i + 1, sum - nums[i]))
                return true;
        }
        
        bad_sum.emplace(sum);
        return false;
    }
    

    '''


Log in to reply
 

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