Skip to main content
Talentd

Prime Subset Selection II - Solution & Explanation

Hard4 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You get an array of integers and must choose a subset that satisfies a prime-based condition. The goal is to find the best valid selection, usually the largest or the one that meets a count or sum target. Primality checks are the bottleneck, so precompute them once.

Approach 1: Brute Force Over All Subsets (O(2^n * n) time, O(n) space)

Generate every subset with recursion or bitmasks from 0 to 2^n - 1. For each subset, test the prime condition by checking each element with trial division up to its square root. Keep the best valid subset seen so far. This works only for small n, since the subset count doubles with every element. Use it to confirm your understanding of the constraint before optimizing.

Approach 2: Backtracking with Pruning (O(2^n) worst case, O(n) space)

Build the subset one element at a time and drop branches early. If the current partial selection already violates the condition, or cannot reach the best answer found so far, stop. Pruning helps a lot on inputs with many invalid elements, but the worst case stays exponential. Prefer this when the constraint is monotone, meaning once a partial set fails, every superset fails too.

Approach 3: Sieve Plus Dynamic Programming (O(n * k + M log log M) time, O(M + n * k) space)

Run the Sieve of Eratosthenes once up to the maximum value M to mark primes in O(M log log M). Then replace repeated primality tests with an O(1) lookup. Model the selection as a DP table where each state tracks the best result for a prefix of the array and a small parameter, such as the number of chosen elements or the running sum modulo a value. Each element either joins the subset or gets skipped, so the transition is constant time per state. This turns exponential enumeration into polynomial work.

Recommended for interviews: Interviewers expect you to start with brute force to show you understand the search space, then move to the sieve and DP approach. The brute force shows correctness reasoning. The sieve plus DP shows you can separate precomputation from the main loop and recognize overlapping subproblems. Explain the state definition and the transition before you write code.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Over SubsetsO(2^n * n)O(n)Very small n, verifying correctness
Backtracking with PruningO(2^n) worst caseO(n)Many invalid elements, monotone constraints
Sieve Plus Dynamic ProgrammingO(n * k + M log log M)O(M + n * k)General case, large n with bounded values

Video Solutions (4)

Leetcode 4081 | Prime Subset Selection II | Leetcode weekly contest 523 | Dynamic Programming

CodeWithMeGuys23:09290 views
Video 1 of 4

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Prime Subset Selection II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Prime Subset Selection I