My Simple C++ DP Code with Comments


  • 8
    S
    class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            int sum = accumulate(nums.begin(), nums.end(), 0);
            if (sum & 1) return false;
            int half = sum >> 1;
            
            vector<bool> accessibility(half + 1, false);
            accessibility[0] = true;    // '0' is always reachable
            //For all num in nums, check the accessibility from half - num to 0. 
            //If 'i' is accessible by former numbers, then 'i + num' is also accessible. (DP Algorithm)
            for(auto num : nums) 
           //Below here we must start from 'half' downto 'num', otherwise current 'num' might be multiply used. 
           //e.g.: If num == 2, then we will have 2, 4, 6... will all be accessible and lead to wrong answer. 
                for(int i = half; i >= num; i--){
                    if (accessibility[i - num] == true){
                        accessibility[i] = true;
                    }
                }
            return accessibility[half];
        }
    };
    

  • 0
    R

    thanks for your explanation


  • 0

    @SGM great solution! Here's my solution which uses the same "accessibility" concept. I have also written a verbose explanation to go along with my thought process. I hope this helps folks to better understand this problem and solution!...

    https://discuss.leetcode.com/topic/103646/very-easy-to-understand-c-with-explanation


Log in to reply
 

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