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


  • 1

    @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


  • 1
    Z

    your solution is really great. and easily to be understood. thank you


Log in to reply
 

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