All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Sanket and Laptops
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

As Sanket has become Red Coder now, so he wants to participate in as many contests as possible. Sanket owns N laptops, and he takes parts in the contest using each laptop so he can make submission for each problems as fast as possible (He is the Top Coder after all!).

But many of his friends are jealous of him. So they decided to challenge him. They asked him to assign a number to each of his laptop. After that, they told Sanket that he can use the laptops in such a manner that no two contest have the same sum when the numbers on the laptops used in that contests are added.

Now, Sanket want to take part in as many contests as possible, but as he is too busy with his preparations for ACM-ICPC, he asks for your help. Determine the maximum number of contests he can participate in, keeping in mind the challenge given by his friends.

Note : Sanket can take part in a contest even if he does not use a laptop.

Input:

First line contains t, the number of test cases.

Each test case consists of 2 lines: the first one contains N (the number of Laptops that Sanket has) and the second line contains N space separated numbers assigned by Sanket to his Laptops denoted by a[i].

Output:

For each test case you need to print a single integer denoting the maximum number of contests that Sanket would be able to participate in.

Constraints:

1<=t<=20

1<=N<=20

1<=a[i]<=100

SAMPLE INPUT
1
3
1 2 3
SAMPLE OUTPUT
7
Explanation

In the given test case t = 1.

We have laptops numbered 1,2 and 3.

So, all the different possibilities are:

{} - Sum=0

{1} - Sum=1

{2} - Sum=2

{3} - Sum=3

{1,2} - Sum=3

{1,3} - Sum=4

{2,3} - Sum=5

{1,2,3} - Sum=6

So, we see that 7 different sums are possible (3 is counted only once) and so output is 7.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications