class Solution { public int minDifference(int arr[], int n) { // int n = arr.length; int k = 0; for(int t : arr) k += t; //find all subset sums equal to total of k ,then traverse the last row //if it is true fin min difference by (totsum - dp[n-1][j]); boolean[][] dp = new boolean[n][k+1]; for(int i = 0 ;i < n ; i++){ for(int j = 0 ; j < k+1 ; j++){ if(i == 0){ if(j == 0 || j-arr[0] == 0) dp[i][j] = true; else dp[i][j] = false; } else{ boolean take = false , notake = false; if(j-arr[i] >= 0) take = dp[i-1][j-arr[i]]; notake = dp[i-1][j]; dp[i][j] = take||notake; } } } int ans= (int)1e9; for(int j = 0 ;j < k+1 ; j++){ if(dp[n-1][j]) ans = Math.min(ans , Math.abs((k-j) - j )); } return ans; } //Recursion -> 2^(n*k) Memoization-> 2*n*k | SC- n*k + n*k public static boolean solve(int arr[] ,int idx , int k , Boolean[][] dp){ if(k < 0) return false; if(idx == 0){ if(k == 0 || k - arr[0]== 0) return true; return false; } if(dp[idx][k] != null) return dp[idx][k]; //take / notake faith calls from (n-1,k) boolean take = solve(arr ,idx-1 , k-arr[idx] , dp ); boolean notake = solve(arr , idx-1 , k , dp); return dp[idx][k] = take||notake; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter