Facebook phone screen - Count subsets

Recruiter contacted me, and asked for availblity in next 4 days.

Status: Working as a Software Engineer in New Jersey
Position: Software Engineer
Location: Menlo Park, CA

Technical Phone Screen - I


Given an array A of
-no duplicate

A positive integer k


Count of all such subsets of A,
Such that for any such subset S,
Min(S) + Max(S) = k
subset should contain atleast two elements

  1. Backtracking approach to get subsets
  2. Get min and max of subset
  3. Add min and max and put them in Hashmap (or update the count)
  4. repeat this process for all subsets
  5. search for k in hashmap and return count of k

input: {1,2,3,4,5}

1, 2, 3, 4, 5, {1,2},{1,3}
k = 5

count = 5

{1, 4},{2,3} {1,2,4}, {1,2,3,4} {1,3,4}


(Discuss the time and space complexity)