Is Prime Subset Selection II easy or hard?

It is rated Hard, with an acceptance rate of about 37.3%. The difficulty comes from identifying the DP state and separating precomputation from the main loop. If you have solved standard subset and DP problems, the main idea becomes manageable with practice.

Prime Subset Selection II Python solution?

In Python, build a sieve as a list of booleans up to the maximum value, then loop over the array while updating a DP list. Use list indexing for prime lookups so each check is O(1). Keep the DP update inside a single loop to avoid extra overhead on large inputs.

How to solve Prime Subset Selection II in O(n)?

Precompute primality with a sieve, then scan the array once while maintaining a DP state that carries the best result so far. Each element is handled in constant time using a lookup into the precomputed prime table. Keep the state small so each update stays O(1).

What is the best approach for Prime Subset Selection II?

The best approach is a sieve of Eratosthenes to precompute primality, combined with dynamic programming over the array. This replaces exponential subset enumeration with polynomial work. The sieve runs once, and each DP transition then takes constant time.

What data structure is used in Prime Subset Selection II?

The solution uses a boolean array for the sieve, which stores primality for every value up to M. The DP step uses a one-dimensional or two-dimensional array to store the best result for each state. Hash sets are not needed because values are bounded and indexable.

What is the time complexity of Prime Subset Selection II?

The optimal solution runs in O(n * k + M log log M) time, where n is the array length, k is the size of the DP state dimension, and M is the maximum value. The brute force alternative runs in O(2^n * n), which becomes infeasible beyond small inputs.

Is Prime Subset Selection II asked at Google, Amazon, or Meta?

This problem is tagged as General on LeetCode, so it does not map to a single company's question bank. Subset selection with prime checks appears in interview rounds that test dynamic programming and number theory fundamentals. Practice the sieve and DP pattern, since it transfers to many similar problems.

4081. Prime Subset Selection II - Practice Online

You are given two integers n and s.

Consider all prime numbers less than or equal to n. Select a subset of these primes such that:

Each prime can be selected at most once.
The sum of the selected primes is as large as possible while remaining less than or equal to s.
Among subsets with the maximum sum, select one containing the fewest primes.
If multiple subsets remain tied, select the one whose elements, written in increasing order, form the lexicographically smallest array.

Return an integer array containing the selected primes in increasing order. If no valid non-empty subset exists, return an empty array.

Example 1:

Input: n = 7, s = 20

Output: [2, 3, 5, 7]

Explanation:

The prime numbers less than or equal to n = 7 are 2, 3, 5, and 7.
The sum of all these primes is 2 + 3 + 5 + 7 = 17, which is less than or equal to s = 20.
Thus, the answer is [2, 3, 5, 7].

Example 2:

Input: n = 15, s = 18

Output: [5,13]

Explanation:

The prime numbers less than or equal to 15 are 2, 3, 5, 7, 11, and 13.
The subsets with sum 18 are [5, 13], [7, 11], [2, 3, 13], and [2, 5, 11]. Since this sum equals s, it is the maximum possible sum.
Among these subsets, [5, 13] and [7, 11] contain the fewest primes: two.
Between these two subsets, [5, 13] is lexicographically smaller because its first element, 5, is smaller than 7. Thus, the answer is [5, 13].

Example 3:

Input: n = 5, s = 1

Output: []

Explanation:

The smallest prime number is 2, which is greater than s = 1.
Thus, no prime can be selected, so the answer is an empty array.

Constraints:

1 <= n <= 1000
1 <= s <= 1000