Subset Sum Problem

Given an array of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

• Time : O(nsum)
• Space : O(sum)

class Solution {
public:
    bool isSubsetSum(vector<int> arr, int sum) {
        vector<bool> dp(sum + 1);
        dp[0] = true;
        for(auto& a : arr) {
            for(int i = sum; i >= a and !dp[sum]; i--) {
                if(dp[i-a]) dp[i] = true;
            }
            if(dp[sum]) break;
        }
        
        return dp[sum];
    }
};