Kolikot

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
 
public class Kolikot {
    
    public static void main(String[] args) 
    {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
	List clear = new ArrayList();
        int[] arr = new int[n];
	int k = 1;
	int max = 0;        
 
        for(int i = 0; i < n; i++)
        {
            arr[i] = scan.nextInt();
            if(arr[i] > max)
                max = arr[i];
            clear.add(arr[i]);
        }
        clear.sort(null);
        
        while(k == (int)(clear.get(0)))
        {
            k++;
            clear.remove(0);
        }
        
        while(isSubsetSum1(arr, n, k))
        {
            k++;
            if(k > max)
                continue;
            while(k == (int)(clear.get(0)))
            {
                k++;
                clear.remove(0);
                if(clear.isEmpty())
                    break;
            }
        }
        System.out.println(k);
    }
    
    static boolean isSubsetSum1(int arr[], int n, int sum) {
 
        boolean[][] subset = new boolean[sum + 1][n + 1];
        int i, j;
 
        for (i = 0; i <= n; i++) {
            subset[0][i] = true;
        }
 
        for (i = 1; i <= sum; i++) {
            subset[i][0] = false;
        }
 
        for (i = 1; i <= sum; i++) {
            for (j = 1; j <= n; j++) {
                subset[i][j] = subset[i][j - 1];
 
                if (i >= arr[j - 1]) {
                    subset[i][j] = subset[i][j] || subset[i - arr[j - 1]][j - 1];
                }
            }
        }
        return subset[sum][n];
    } 
}
 

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED