# Subset Sum – HackerRank Solution

In this post, we will solve Subset Sum HackerRank Solution. This problem (Subset Sum) is a part of HackerRank Functional Programming series.

You are given a list of N positive integers, A = {a[1], a[2], …, a[N]} and another integer S. You have to find whether there exists a non-empty subset of A whose sum is greater than or equal to S.

You have to print the size of minimal subset whose sum is greater than or equal to S. If there exists no such subset then printÂ `-1`Â instead.

## Input

First line will contain an integer,Â N, which is the size of listÂ A. Second line containsÂ NÂ space separated integers, representing the elements of listÂ A. In third line there is an integer,Â T, which represent the number of test cases to follow. Then followsÂ TÂ lines. Each one of them contains an single integer,Â S.

## Output

For each test case, print the size of minimal subset whose sum is greater than or equal toÂ S. If there’s no such subset then printÂ `-1`.

## Constraints

• 1 â‰¤Â NÂ â‰¤ 105
• 1 â‰¤ a[i] â‰¤ 109
• 1 â‰¤Â TÂ â‰¤ 105
• 1 â‰¤Â SÂ â‰¤ 1015

Note
Two subsets are different if there’s an elementÂ a[i]Â which exists in one of them and not in other. That is, for setÂ `A = {4, 4}`Â there are four possible subsetsÂ `{}`,Â `{a[1]}`,Â `{a[2]}`Â andÂ `{a[1], a[2]}`.

Sample Input

``````4
4 8 10 12
4
4
13
30
100``````

Sample Output

``````1
2
3
-1``````

Explanation

Sample Case #00:Â ForÂ `S = 4`, we can select any one element of setÂ AÂ as each of them is greater than or equal to 4.
Sample Case #01:Â There are many possible subsets of size 2 whose sum is not less thanÂ 13. They areÂ `{4, 10}`,Â `{4, 12}`,Â `{8, 10}`,Â `{8, 12}`Â andÂ `{10, 12}`.
Sample Case #02:Â SubsetÂ `{8, 10, 12}`, with sum 30, is the only subset of size 3 whose sum is not less thanÂ `S = 30`.
Sample Case #03:Â Even after selecting all the elements ofÂ A, we can’t exceedÂ `S = 100`.

## Solution – Subset Sum – HackerRank Solution

Scala

```import java.util.Scanner

import scala.collection.Searching._

object Solution {
def main(args: Array[String]): Unit = {
val sc = new Scanner(System.in)

sc.nextLine
val a = sc.nextLine.split(' ').map(_.toLong).sortBy(-_)

var sum = 0L
val sums = a.map(v => {
sum += v
sum
})

val t = sc.nextInt
(0 until t).foreach(_ => {
val s = sc.nextLong

val count = (sums.search(s) match {
case InsertionPoint(i) => i
case Found(i) => i
}) + 1
println(if (count <= a.length) count else -1)
})
}
}
```

Note: This problem (Subset Sum) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.