Fully documented C++ DP Solution (22ms)


  • 0
    P

    I spent lot of time reading other answers and explanations from other sites and struggled to really get the DP solution. I think I finally got it and wanted to document my understanding in the comments. Other than the basic algorithm I have not spent time in optimizing the time. It runs at 22ms. I am using the 1-D DP method. It runs in O(nk) time and O(nk) space. n=array size, k=sum of all elements

    class Solution {
    public:
        
        bool subset_sum(const vector<int>& a, int target)
        {
            /* subset_sum problem is NP-Complete. So, basic recursive solution
               would be exponential time. We can solve this with dynamic programming
               in O(nk) time (n=array size, k=target) using O(k) space.
               
               each index in dp[] array corresponds to a sum value. dp[s] is true
               if sum s can be obtained from the subset of this array.
               
               if we are looking at an element of the array x, dp[s] can be set to 
               true of dp[s-x] is true. This is because if sum (s-x) is possible then
               adding x to that sum will get us to sum s. Finally, building up this
               dp array can give us the final answer at dp[target] */
            
            vector<bool> dp(target + 1);
            
            /* dp[0] is true, as we can always get sum of 0 using an empty set */
            dp[0] = true;
            
            /* for each element in array, update the dp array */
            for (int x : a) {
                
                /* iterating from right to left in dp array, as we are going to
                   refer to smaller (s-x) index when updating index s. We dont want
                   dp[s-x] updated before dp[s] */
                for (int s = target; s > 0; s--) {
                    if (s >= x && dp[s - x] == true) {
                        dp[s] = true;
                        /* if target sum is found, we can return immediately */
                        if (s == target) {
                            return true;
                        }
                    }
                }
            }
            /* if target sum is never set to true, we will reach here */
            return false;
        }
        
        bool canPartition(vector<int>& nums)
        {   
            /* find sum of all elements in array */
            int sum = 0;
            for (int x : nums) {
                sum += x;
            }
            /* we can partition the array into two equal values, only if total sum
               of the elements is even. So, return false if sum is odd */
            if (sum % 2 != 0) {
                return false;
            }
            
            /* now, the problem becomes more clear. We need to check if there is a
               subset of elements in the array whose total is sum/2. This is a well
               known subset sum problem */
            return subset_sum(nums, sum/2);
        }
    };
    

Log in to reply
 

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