educative.io

Space O(S) java 1D array solution

Courses
,
#1 
//1d array solution
class PartitionSet {

  public int canPartition(int[] num) {
    // bottom up
    int sum = 0;
    int n = num.length;
    for(int number: num){
      sum += number;
    }

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

    for(int i = 1; i < n; i++){
      for(int s = sum/2; s >= 0; s--){
        if(dp[s] == false && s >= num[i]){
          dp[s] = dp[s - num[i]];
        }
      }
    }
    int sum1 = 0;
    for(int s = sum/2; s >= 0; s--){
      if(dp[s]){
        sum1 = s;
        break;
      }   
    }
    int sum2 = sum - sum1;
    return Math.abs(sum1 - sum2);
  }

  public static void main(String[] args) {
    PartitionSet ps = new PartitionSet();
    int[] num = {1, 2, 3, 9};
    System.out.println(ps.canPartition(num));
    num = new int[]{1, 2, 7, 1, 5};
    System.out.println(ps.canPartition(num));
    num = new int[]{1, 3, 100, 4};
    System.out.println(ps.canPartition(num));
  }
}

Type your question above this line.

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