educative.io

Educative

Space complexity O(S) 1D array java solution

class PartitionSet {

  static boolean canPartition(int[] num) {
    //bottom up
    
    int sum = 0;
    for(int n : num){
      sum += n;
    }
    if((sum % 2) == 1){
      return false;
    }
      
    sum /= 2;
    int l = num.length;
    boolean[]dp = new boolean[sum + 1];
    dp[0] = true;

    for(int s = 1; s <= sum; s++){
      dp[s] = ( num[0] == s ? true : false);
    }

    for(int i = 1; i < l; i++){
      for(int s = sum; s > 0; s--){    
        if(dp[s] == false && s >= num[i]){
          dp[s] = dp[s - num[i]];
        }
      }
    }

    return dp[sum];
  }
}

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5633779737559040
Lesson: https://www.educative.io/collection/page/5668639101419520/5633779737559040/5752754626625536