Largest Divisible Subset

🎯

Largest Divisible Subset

mediumBACKTRACKINGAmazonGoogleMicrosoft

Imagine you have a collection of files with sizes, and you want to find the largest group where each file size divides the next one perfectly, ensuring compatibility in a chain.

💡 This problem asks for the largest subset of numbers where every pair satisfies a divisibility condition. Beginners often struggle because it combines subset generation with a divisibility constraint, which is not straightforward to brute force efficiently.

📋

Problem Statement

Given a set of distinct positive integers nums, find the largest subset such that for every pair (Si, Sj) in the subset, either Si % Sj == 0 or Sj % Si == 0. Return the largest subset. If there are multiple answers, return any of them.

1 ≤ nums.length ≤ 10^51 ≤ nums[i] ≤ 10^9All elements of nums are distinct

💡

Example

Input"[1, 2, 3]"

Output[1, 2]

1 divides 2, so [1, 2] is a valid divisible subset. [1, 3] is also valid but same size. Largest size is 2.

Input"[1, 2, 4, 8]"

Output[1, 2, 4, 8]

All numbers form a chain where each divides the next, so the entire array is the largest divisible subset.

• Single element array → output is the element itself
• Array with all prime numbers → output is any single element
• Array with multiple chains of same length → output any largest chain
• Array with large numbers and gaps → ensure no overflow or incorrect divisibility

⚠️

Common Mistakes

Not sorting the input array

Divisibility checks become incorrect or inefficient, leading to wrong answers or TLE

✅ Always sort nums before DP to ensure chain building is valid

Not reconstructing the subset correctly

Return length only or incorrect subset, failing interview expectations

✅ Use a prev array to track predecessors and reconstruct the subset after DP

Checking divisibility incorrectly (e.g., nums[j] % nums[i])

Wrong divisibility logic leads to invalid subsets

✅ Check nums[i] % nums[j] == 0 since nums[i] is larger after sorting

Using brute force for large inputs

Code times out or crashes due to exponential complexity

✅ Use DP approach for efficiency

🧠

Brute Force (Pure Recursion / Nested Loops / etc.)

💡 Starting with brute force helps understand the problem deeply by exploring all subsets and checking divisibility, even though it's inefficient. Think of it as trying every possible team combination to find the best fit, which is simple but slow.

Intuition

Try every subset of nums and check if it satisfies the divisibility condition. Keep track of the largest valid subset found.

Algorithm

1. Generate all subsets of nums using recursion or bitmask.
2. For each subset, check if every pair satisfies the divisibility condition.
3. Keep track of the largest valid subset found so far.
4. Return the largest valid subset after checking all.

💡 This approach is conceptually simple but hard to implement efficiently because the number of subsets grows exponentially.

</>

Code

from typing import List

def largestDivisibleSubset(nums: List[int]) -> List[int]:
    n = len(nums)
    nums.sort()
    max_subset = []

    def is_divisible_subset(subset):
        for i in range(len(subset)):
            for j in range(i + 1, len(subset)):
                if subset[j] % subset[i] != 0:
                    return False
        return True

    def backtrack(start, path):
        nonlocal max_subset
        if len(path) > len(max_subset):
            if is_divisible_subset(path):
                max_subset = path[:]
        for i in range(start, n):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return max_subset

# Driver code
if __name__ == '__main__':
    print(largestDivisibleSubset([1, 2, 3]))  # Expected: [1, 2] or [1, 3]

Line Notes

nums.sort()Sorting helps to check divisibility in ascending order, simplifying checks.

def is_divisible_subset(subset):Helper to verify if current subset satisfies divisibility condition.

for i in range(len(subset))Check every pair in the subset for divisibility to ensure the subset is valid.

if len(path) > len(max_subset):Update max subset only if current path is longer and valid to keep track of largest subset.

import java.util.*;

public class LargestDivisibleSubset {
    public static List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        List<Integer> maxSubset = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), maxSubset);
        return maxSubset;
    }

    private static void backtrack(int[] nums, int start, List<Integer> path, List<Integer> maxSubset) {
        if (path.size() > maxSubset.size() && isDivisibleSubset(path)) {
            maxSubset.clear();
            maxSubset.addAll(path);
        }
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path, maxSubset);
            path.remove(path.size() - 1);
        }
    }

    private static boolean isDivisibleSubset(List<Integer> subset) {
        for (int i = 0; i < subset.size(); i++) {
            for (int j = i + 1; j < subset.size(); j++) {
                if (subset.get(j) % subset.get(i) != 0) return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(largestDivisibleSubset(new int[]{1, 2, 3})); // Expected: [1, 2] or [1, 3]
    }
}

Line Notes

Arrays.sort(nums);Sort to simplify divisibility checks in ascending order.

if (path.size() > maxSubset.size() && isDivisibleSubset(path))Update max subset only if current path is longer and valid to track largest subset.

for (int i = start; i < nums.length; i++)Try adding each remaining number to current subset to explore all subsets.

path.remove(path.size() - 1);Backtrack by removing last added element to explore other subsets.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool isDivisibleSubset(const vector<int>& subset) {
    for (int i = 0; i < (int)subset.size(); i++) {
        for (int j = i + 1; j < (int)subset.size(); j++) {
            if (subset[j] % subset[i] != 0) return false;
        }
    }
    return true;
}

void backtrack(const vector<int>& nums, int start, vector<int>& path, vector<int>& maxSubset) {
    if ((int)path.size() > (int)maxSubset.size() && isDivisibleSubset(path)) {
        maxSubset = path;
    }
    for (int i = start; i < (int)nums.size(); i++) {
        path.push_back(nums[i]);
        backtrack(nums, i + 1, path, maxSubset);
        path.pop_back();
    }
}

vector<int> largestDivisibleSubset(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<int> maxSubset, path;
    backtrack(nums, 0, path, maxSubset);
    return maxSubset;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<int> res = largestDivisibleSubset(nums);
    for (int x : res) cout << x << ' ';
    cout << '\n'; // Expected: 1 2 or 1 3
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort to ensure divisibility checks are easier and consistent.

if ((int)path.size() > (int)maxSubset.size() && isDivisibleSubset(path))Update max subset only if current path is longer and valid to track largest subset.

path.push_back(nums[i]);Add current number to subset before recursive call to explore subsets.

path.pop_back();Remove last number to backtrack and try other subsets.

function largestDivisibleSubset(nums) {
    nums.sort((a, b) => a - b);
    let maxSubset = [];

    function isDivisibleSubset(subset) {
        for (let i = 0; i < subset.length; i++) {
            for (let j = i + 1; j < subset.length; j++) {
                if (subset[j] % subset[i] !== 0) return false;
            }
        }
        return true;
    }

    function backtrack(start, path) {
        if (path.length > maxSubset.length && isDivisibleSubset(path)) {
            maxSubset = path.slice();
        }
        for (let i = start; i < nums.length; i++) {
            path.push(nums[i]);
            backtrack(i + 1, path);
            path.pop();
        }
    }

    backtrack(0, []);
    return maxSubset;
}

// Test
console.log(largestDivisibleSubset([1, 2, 3])); // Expected: [1, 2] or [1, 3]

Line Notes

nums.sort((a, b) => a - b);Sort to make divisibility checks straightforward and consistent.

if (path.length > maxSubset.length && isDivisibleSubset(path))Update max subset only if current path is longer and valid to track largest subset.

path.push(nums[i]);Add current element before recursive exploration to build subsets.

path.pop();Backtrack by removing last element to try other subsets.

⏱

Complexity

TimeO(n * 2^n * n^2)

SpaceO(n)

There are 2^n subsets, each subset can be up to size n, and checking divisibility takes O(n^2) in worst case.

💡 For n=20, this means over a million subsets and billions of checks, which is impractical. This approach is mainly for understanding the problem.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and correctness.

🧠

Sorting + Dynamic Programming (Longest Chain Building)

💡 Sorting the array and using DP to build the largest divisible subset ending at each element reduces complexity drastically. Think of it as stacking blocks where each block fits perfectly on a smaller one.

Intuition

Sort nums so divisibility checks only need to consider previous elements. For each number, find the longest divisible subset ending with it by extending smaller divisible subsets.

Algorithm

1. Sort nums in ascending order.
2. Create a DP array where dp[i] stores the size of the largest divisible subset ending with nums[i].
3. For each nums[i], check all nums[j] with j < i; if nums[i] % nums[j] == 0, update dp[i] = max(dp[i], dp[j] + 1).
4. Track the maximum dp value and reconstruct the subset by backtracking.

💡 This approach uses the idea that a divisible subset ending at i can be built by extending a smaller subset ending at j if divisibility holds.

Recurrence:dp[i] = max(dp[j] + 1) for all j < i where nums[i] % nums[j] == 0, else 1

</>

Code

from typing import List

def largestDivisibleSubset(nums: List[int]) -> List[int]:
    if not nums:
        return []
    nums.sort()
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n
    max_index = 0

    for i in range(n):
        for j in range(i):
            if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j
        if dp[i] > dp[max_index]:
            max_index = i

    result = []
    while max_index >= 0:
        result.append(nums[max_index])
        max_index = prev[max_index]
    return result[::-1]

# Driver code
if __name__ == '__main__':
    print(largestDivisibleSubset([1, 2, 3]))  # Expected: [1, 2]

Line Notes

nums.sort()Sorting ensures divisibility checks only need to consider previous elements, simplifying logic.

dp = [1] * nInitialize dp with 1 since each element alone forms a subset of size 1.

if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:Update dp[i] if nums[i] can extend the subset ending at nums[j].

while max_index >= 0:Reconstruct the subset by following the prev pointers to get the actual subset.

import java.util.*;

public class LargestDivisibleSubset {
    public static List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] dp = new int[n];
        int[] prev = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(prev, -1);
        int maxIndex = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
            if (dp[i] > dp[maxIndex]) {
                maxIndex = i;
            }
        }

        List<Integer> result = new ArrayList<>();
        while (maxIndex >= 0) {
            result.add(nums[maxIndex]);
            maxIndex = prev[maxIndex];
        }
        Collections.reverse(result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(largestDivisibleSubset(new int[]{1, 2, 3})); // Expected: [1, 2]
    }
}

Line Notes

Arrays.sort(nums);Sort to ensure divisibility checks only consider previous elements, simplifying the problem.

Arrays.fill(dp, 1);Each element alone forms a subset of size 1 initially.

if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i])Update dp[i] if nums[i] can extend the subset ending at nums[j].

while (maxIndex >= 0)Reconstruct the subset by following prev indices to retrieve the actual subset.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> largestDivisibleSubset(vector<int>& nums) {
    if (nums.empty()) return {};
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<int> dp(n, 1), prev(n, -1);
    int maxIndex = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
        if (dp[i] > dp[maxIndex]) maxIndex = i;
    }

    vector<int> result;
    while (maxIndex >= 0) {
        result.push_back(nums[maxIndex]);
        maxIndex = prev[maxIndex];
    }
    reverse(result.begin(), result.end());
    return result;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<int> res = largestDivisibleSubset(nums);
    for (int x : res) cout << x << ' ';
    cout << '\n'; // Expected: 1 2
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort to simplify divisibility checks and ensure correct chain building.

vector<int> dp(n, 1), prev(n, -1);Initialize dp and prev arrays for chain length and reconstruction.

if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i])Update dp[i] and prev[i] if extending chain is possible.

while (maxIndex >= 0)Reconstruct the largest divisible subset by following prev pointers.

function largestDivisibleSubset(nums) {
    if (nums.length === 0) return [];
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const dp = new Array(n).fill(1);
    const prev = new Array(n).fill(-1);
    let maxIndex = 0;

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] % nums[j] === 0 && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
        if (dp[i] > dp[maxIndex]) maxIndex = i;
    }

    const result = [];
    while (maxIndex >= 0) {
        result.push(nums[maxIndex]);
        maxIndex = prev[maxIndex];
    }
    result.reverse();
    return result;
}

// Test
console.log(largestDivisibleSubset([1, 2, 3])); // Expected: [1, 2]

Line Notes

nums.sort((a, b) => a - b);Sort to ensure divisibility checks only consider previous elements, simplifying logic.

const dp = new Array(n).fill(1);Initialize dp array with 1 for single element subsets.

if (nums[i] % nums[j] === 0 && dp[j] + 1 > dp[i])Update dp[i] and prev[i] if nums[i] can extend the subset ending at nums[j].

while (maxIndex >= 0)Reconstruct the subset by following prev indices to get the actual subset.

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Nested loops check divisibility for each pair, and dp arrays store chain lengths and predecessors for reconstruction.

💡 For n=1000, this means about 1 million operations, which is feasible in interviews and much faster than brute force.

Interview Verdict: Accepted

This approach balances clarity and efficiency, suitable for coding in interviews.

🧠

Optimized DP with Early Break (Minor Improvement)

💡 By sorting and breaking early when divisibility fails, we slightly reduce unnecessary checks, improving runtime in practice. This is like stopping a search early when you know no further candidates can improve the chain.

Intuition

Since nums is sorted, if nums[i] % nums[j] != 0 for some j, and nums[j] is large, further j's might also fail, so break early to save time.

Algorithm

1. Sort nums ascending.
2. Initialize dp and prev arrays as before.
3. For each i, iterate j from i-1 down to 0, break early if divisibility fails.
4. Update dp[i] and prev[i] accordingly.
5. Reconstruct the largest subset from dp and prev.

💡 Early break reduces the number of divisibility checks, improving average runtime without changing worst-case complexity.

Recurrence:Same as previous approach.

</>

Code

from typing import List

def largestDivisibleSubset(nums: List[int]) -> List[int]:
    if not nums:
        return []
    nums.sort()
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n
    max_index = 0

    for i in range(n):
        for j in range(i - 1, -1, -1):
            if nums[i] % nums[j] == 0:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    prev[i] = j
            else:
                # Early break since nums is sorted
                break
        if dp[i] > dp[max_index]:
            max_index = i

    result = []
    while max_index >= 0:
        result.append(nums[max_index])
        max_index = prev[max_index]
    return result[::-1]

# Driver code
if __name__ == '__main__':
    print(largestDivisibleSubset([1, 2, 3]))  # Expected: [1, 2]

Line Notes

for j in range(i - 1, -1, -1):Iterate backwards to enable early break on failure, improving efficiency.

if nums[i] % nums[j] == 0:Check divisibility to extend chain if possible.

else: breakBreak early to avoid unnecessary checks due to sorted order guaranteeing no further divisibility.

while max_index >= 0:Reconstruct the subset by following prev pointers to retrieve the largest subset.

import java.util.*;

public class LargestDivisibleSubset {
    public static List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] dp = new int[n];
        int[] prev = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(prev, -1);
        int maxIndex = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] % nums[j] == 0) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        prev[i] = j;
                    }
                } else {
                    break;
                }
            }
            if (dp[i] > dp[maxIndex]) {
                maxIndex = i;
            }
        }

        List<Integer> result = new ArrayList<>();
        while (maxIndex >= 0) {
            result.add(nums[maxIndex]);
            maxIndex = prev[maxIndex];
        }
        Collections.reverse(result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(largestDivisibleSubset(new int[]{1, 2, 3})); // Expected: [1, 2]
    }
}

Line Notes

for (int j = i - 1; j >= 0; j--)Iterate backwards to allow early break optimization, reducing unnecessary checks.

if (nums[i] % nums[j] == 0)Check divisibility to extend chain if possible.

else { break; }Break early to skip further checks since nums is sorted and no further divisibility possible.

while (maxIndex >= 0)Reconstruct the subset by following prev indices to get the largest subset.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> largestDivisibleSubset(vector<int>& nums) {
    if (nums.empty()) return {};
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<int> dp(n, 1), prev(n, -1);
    int maxIndex = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (nums[i] % nums[j] == 0) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            } else {
                break;
            }
        }
        if (dp[i] > dp[maxIndex]) maxIndex = i;
    }

    vector<int> result;
    while (maxIndex >= 0) {
        result.push_back(nums[maxIndex]);
        maxIndex = prev[maxIndex];
    }
    reverse(result.begin(), result.end());
    return result;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<int> res = largestDivisibleSubset(nums);
    for (int x : res) cout << x << ' ';
    cout << '\n'; // Expected: 1 2
    return 0;
}

Line Notes

for (int j = i - 1; j >= 0; j--)Iterate backwards to enable early break optimization, improving average runtime.

if (nums[i] % nums[j] == 0)Check divisibility to extend chain if possible.

else { break; }Break early to avoid unnecessary checks due to sorted order.

while (maxIndex >= 0)Reconstruct the subset by following prev pointers to retrieve the largest subset.

function largestDivisibleSubset(nums) {
    if (nums.length === 0) return [];
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const dp = new Array(n).fill(1);
    const prev = new Array(n).fill(-1);
    let maxIndex = 0;

    for (let i = 0; i < n; i++) {
        for (let j = i - 1; j >= 0; j--) {
            if (nums[i] % nums[j] === 0) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            } else {
                break;
            }
        }
        if (dp[i] > dp[maxIndex]) maxIndex = i;
    }

    const result = [];
    while (maxIndex >= 0) {
        result.push(nums[maxIndex]);
        maxIndex = prev[maxIndex];
    }
    result.reverse();
    return result;
}

// Test
console.log(largestDivisibleSubset([1, 2, 3])); // Expected: [1, 2]

Line Notes

for (let j = i - 1; j >= 0; j--)Iterate backwards to allow early break optimization, reducing unnecessary checks.

if (nums[i] % nums[j] === 0)Check divisibility to extend chain if possible.

else { break; }Break early to reduce unnecessary checks due to sorted order.

while (maxIndex >= 0)Reconstruct the subset by following prev indices to get the largest subset.

⏱

Complexity

TimeO(n^2) worst case, but faster in practice due to early breaks

SpaceO(n)

Early breaks reduce average checks but worst case remains quadratic. The sorted order allows skipping unnecessary divisibility checks.

💡 This optimization helps in real interviews to show attention to detail and efficiency without complicating the code.

Interview Verdict: Accepted

A practical improvement over basic DP, demonstrating optimization skills.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the DP approach with sorting in 95% of interviews for best balance of clarity and performance.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * 2^n * n^2)	O(n)	Yes (deep recursion)	Yes	Mention only - never code
2. Sorting + DP	O(n^2)	O(n)	No	Yes	Code this approach
3. Optimized DP with Early Break	O(n^2) worst case, faster average	O(n)	No	Yes	Mention as optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of the problem.Introduce the DP approach with sorting and chain building.Discuss optimizations like early breaks.Code the DP solution carefully and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 15min → Test: 3min. Total ~25min

What the Interviewer Tests

Understanding of subset generation, divisibility logic, DP formulation, and ability to optimize and reconstruct solution.

Common Follow-ups

• What if numbers are not distinct? → Handle duplicates by sorting and skipping duplicates.
• Can you optimize space? → Space is already O(n), minimal for reconstruction.

💡 These follow-ups test your ability to handle input variations and optimize resource usage.

🔍

Pattern Recognition

When to Use

1) Asked for largest subset with divisibility or chain property, 2) Input is array of distinct positive integers, 3) Subset elements must satisfy pairwise divisibility, 4) Need to return actual subset.

Signature Phrases

largest divisible subsetfor every pair Si, Sj either Si % Sj == 0 or Sj % Si == 0

NOT This Pattern When

Subset sum or knapsack problems which focus on sums rather than divisibility.

Similar Problems

Longest Increasing Subsequence - similar chain building with orderingMaximum Length Chain of Pairs - chain building with pair constraints

Practice

1. You are given a list of candidate numbers (which may contain duplicates) and a target sum. You need to find all unique combinations where each candidate number is used at most once and the sum of the combination equals the target. Which algorithmic approach best guarantees finding all unique combinations without duplicates efficiently?

easy

A. Backtracking with sorting candidates, skipping duplicates at the same recursion level, and pruning branches when the candidate exceeds the remaining target

B. Greedy algorithm that picks the largest candidates first until the target is met or exceeded

C. Dynamic programming subset-sum approach without handling duplicates explicitly

D. Brute force recursion without sorting or duplicate checks, exploring all subsets

Solution

1. Step 1: Understand problem constraints

   The problem requires unique combinations without reuse and no duplicate results, so duplicates must be handled carefully.

2. Step 2: Identify suitable algorithm

   Backtracking with sorting and skipping duplicates at the same recursion level ensures no repeated combinations. Early pruning avoids unnecessary recursion when candidates exceed the target.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + duplicate skipping + pruning is the standard approach [OK]

Hint: Sorting and skipping duplicates avoids repeated combinations [OK]

Common Mistakes:

• Using greedy misses some combinations
• DP without duplicate handling outputs duplicates
• Brute force is correct but inefficient and duplicates appear

2. What is the time complexity of the iterative lexicographic combinations generation algorithm for generating all combinations of size k from n elements?

medium

A. O(n^k) because each element can be chosen or not

B. O(k * (n choose k)) since each combination of size k is generated once and updated in O(k)

C. O(\u03C3(n choose k) * k) where \u03C3 is the number of combinations generated

D. O(n * k) because the outer loop runs n times and inner loop k times

Solution

1. Step 1: Identify number of combinations

   There are exactly (n choose k) combinations to generate.

2. Step 2: Analyze per-combination cost

   Each combination is generated and updated in O(k) time due to copying and resetting elements.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Time is proportional to number of combinations times combination size [OK]

Hint: Time depends on number of combinations times k [OK]

Common Mistakes:

• Confusing with exponential O(n^k) or linear O(n*k) complexities

3. What is the time complexity of the space-optimized DP solution for counting subsets with sum K, given an array of size n and target sum K?

medium

A. O(2^n) because all subsets are explored

B. O(n * K) because the DP iterates over n elements and sums up to K

C. O(n + K) because it processes each element and sum once

D. O(n * K^2) because nested loops iterate over n and K twice

Solution

1. Step 1: Identify loops in the DP

   Outer loop runs n times, inner loop runs up to K times for each element.

2. Step 2: Calculate total operations

   Total operations = n * K, so time complexity is O(n * K).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP iterates over all elements and sums up to K -> O(n * K) [OK]

Hint: DP complexity depends on n and K, not exponential [OK]

Common Mistakes:

• Confusing DP with brute force exponential time
• Assuming linear time due to single loops

4. The following code attempts to count subsets with sum K using space-optimized DP. Identify the line that contains a subtle bug that can cause incorrect results.

def count_subsets_space_optimized(arr, K):
    dp = [0] * (K + 1)
    dp[0] = 1
    for num in arr:
        for j in range(num, K + 1):
            dp[j] += dp[j - num]
    return dp[K]

medium

A. for j in range(num, K + 1):

B. dp[0] = 1

C. dp = [0] * (K + 1)

D. dp[j] += dp[j - num]

Solution

1. Step 1: Analyze iteration order

   The inner loop iterates forward from num to K, which causes dp[j] to use updated dp values from the same iteration, leading to overcounting.

2. Step 2: Correct iteration direction

   To avoid overcounting, the inner loop must iterate backward from K down to num.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Forward iteration in DP causes incorrect counts -> bug in loop range [OK]

Hint: Inner loop must iterate backward to avoid reuse of updated dp values [OK]

Common Mistakes:

• Using forward iteration in space-optimized DP
• Misunderstanding dp update dependencies

5. What is the time complexity of the optimal backtracking solution for letter case permutation on a string of length n with k letters (non-digit characters)?

medium

A. O(2^k * n) because only letters toggle case and each permutation requires joining n characters

B. O(2^k * k) because only letters are toggled and digits are skipped

C. O(n * 2^n) because each character doubles the permutations

D. O(n^2) because of nested recursion and string concatenation

Solution

1. Step 1: Identify branching factor

   Only letters (k of them) cause branching, each with 2 choices, so total permutations are 2^k.

2. Step 2: Calculate work per permutation

   Each permutation requires joining n characters to form a string, so O(n) per permutation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time is exponential in letters, linear in string length [OK]

Hint: Complexity depends on letters, not total length [OK]

Common Mistakes:

• Assuming all characters double permutations
• Ignoring join cost per permutation