package DynamicProgramming;
// Partition a set into two subsets such that the difference of subset sums is minimum

/*
Input:  arr[] = {1, 6, 11, 5}
Output: 1
Explanation:
Subset1 = {1, 5, 6}, sum of Subset1 = 12
Subset2 = {11}, sum of Subset2 = 11

Input:  arr[] = {36, 7, 46, 40}
Output: 23
Explanation:
Subset1 = {7, 46} ;  sum of Subset1 = 53
Subset2 = {36, 40} ; sum of Subset2  = 76
 */

import java.io.*;
import java.util.*;

public class MinimumSumPartition {
  public static int subSet(int[] arr) {
    int n = arr.length;
    int sum = getSum(arr);
    boolean[][] dp = new boolean[n + 1][sum + 1];
    for (int i = 0; i