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.

Task

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 ≤ 10⁵
• 1 ≤ a[i] ≤ 10⁹
• 1 ≤ T ≤ 10⁵
• 1 ≤ S ≤ 10¹⁵

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.