Rotate Image

class Solution {
public:
    bool subsetsum(int n, vector<int> arr, int sum){
        bool dp[n+1][sum+1];
        for(int i=0;i<n+1;i++){
            dp[i][0]=1;
        }
        for(int j=1;j<sum+1;j++){
            dp[0][j]=0;
        }
        
        for(int i=1;i<n+1;i++){
            for(int j=1;j<sum+1;j++){
                if(arr[i-1]<=j){
                    dp[i][j]= (dp[i-1][j-arr[i-1]] || dp[i-1][j]);
                }else{
                    dp[i][j]= dp[i-1][j];
                }
            }
        }
        return dp[n][sum];
    }
    bool canPartition(vector<int>& arr) {
      int sum=0;
      int n=arr.size();  
        for(int i=0;i<n;i++){
            sum+=arr[i];
        }
        if((sum&1)!=0){
            return 0;
        }else{
            return subsetsum(n, arr, sum/2);
        }   
    }
};