Fewest Powers of Two Summing to Target

You are given an integer array nums, where every element is a power of two (1, 2, 4, ..., 2^30), and an integer target.

Select a subset of the elements of nums, using each element at most once, whose sum is exactly target.

Return the minimum number of elements in such a subset, or -1 if no subset of nums sums to target.

Examples

Example 1

Input: nums = [4,8,2,1], target = 13
Output: 3
Explanation: 8 + 4 + 1 = 13 uses three elements; no two elements of nums sum to 13.

Example 2

Input: nums = [2,2,2], target = 6
Output: 3
Explanation: All three elements are needed: 2 + 2 + 2 = 6.

Example 3

Input: nums = [8,4], target = 5
Output: -1
Explanation: The possible sums are 4, 8, and 12, so 5 is unreachable.