Q5 PepCoding | Print All Paths With Target Sum Subset

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));
                }
            }
        }
    }
}