import java.io.*; import java.util.*; public class Main { public static class Pair{ int i; int j; String psf; public Pair(int i, int j, String psf){ this.i = i; this.j = j; this.psf = psf; } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int size = Integer.parseInt(br.readLine()); int[] arr = new int[size]; for (int i = 0; i < size; i++) { arr[i] = Integer.parseInt(br.readLine()); } int tar = Integer.parseInt(br.readLine()); boolean dp[][] = new boolean[arr.length +1][tar+1]; int m = dp.length , n = dp[0].length; //first col will be true for(int i = 0 ; i <m ;i++) dp[i][0] = true; //first row after first element will be false ,default in boolean for(int i = 1 ; i < m ; i++){ for(int j = 1 ; j < n ;j++){ //number will contribute only if it is >= current col target if(j >= arr[i-1] ){ if(dp[i-1][j] || dp[i][j- arr[i-1]]) dp[i][j] = true; } //else previous answer will be stored else { dp[i][j] = dp[i-1][j]; } } } System.out.println(dp[arr.length][tar]); BFS(dp ,arr, tar); } public static void BFS(boolean[][] dp,int[] arr ,int target ){ ArrayDeque<Pair> q = new ArrayDeque<>(); q.add(new Pair(arr.length,target , "")); while(q.size()>0){ Pair rem = q.removeFirst(); int i = rem.i , j = rem.j ; //if we get to first col all numbers will be ignored from this point and we have already reached our answer if(i == 0 || j == 0) System.out.println(rem.psf); /* 2 calls will be made from last coloumn of include and exclude recursive call will stop if encounters false anywhere while retracing */ else{ boolean exec = dp[i-1][j]; if(exec) q.add(new Pair(i-1 ,j , rem.psf)); // i-1 is added as array is i-1 of dp if(j>= arr[i-1]){ boolean inc = dp[i-1][j - arr[i-1]]; if(inc) q.add(new Pair(i-1,j-arr[i-1],(i-1)+" "+ rem.psf)); } } } } }
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