← 返回 pinterest 的题目列表Minimum Pins to Exactly Fill a Screen
类型：online_judge
You are given a collection of Pins, where each Pin has a positive integer height, and a screen height screenHeight.
Each Pin may be used at most once. Select a subset of Pins whose heights sum exactly to screenHeight, and return the minimum number of selected Pins.
Return -1 if it is impossible to fill the screen exactly.
Input Format
Line 1: integer n, the number of Pins.
Line 2: n integers heights[i], the height of each Pin.
Line 3: integer screenHeight.
Output Format
Print the minimum number of Pins needed, or -1 if exact filling is impossible.
Example 1
Input:
4
2 3 5 7
10
Output:
2
Explanation: choose Pins with heights 3 and 7.
Example 2
Input:
3
4 6 8
11
Output:
-1
Constraints
1 <= n <= 10^4
1 <= heights[i] <= 10^4
1 <= screenHeight <= 10^5
Example
Input
4
2 3 5 7
10
Output
2