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 need to generate all possible subsets of a given set of distinct integers. Which approach guarantees generating every subset exactly once with a time complexity proportional to the number of subsets times the size of each subset?

easy

A. Greedy algorithm that picks elements based on their value order

B. Enumerate all bitmasks from 0 to 2^n - 1, selecting elements where bits are set

C. Dynamic programming to count subsets without generating them

D. Sorting the array and using two pointers to find pairs

Solution

1. Step 1: Understand the problem

   We want to generate all subsets of a set, which are 2^n in number.

2. Step 2: Identify the approach that enumerates all subsets

   Bitmask enumeration from 0 to 2^n - 1 maps each bit to an element's inclusion, guaranteeing all subsets exactly once.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask enumeration covers all subsets systematically [OK]

Hint: Bitmask from 0 to 2^n-1 enumerates all subsets [OK]

Common Mistakes:

• Thinking greedy or sorting can generate all subsets efficiently

2. Given the following code to generate subsets, what is the value of result after processing num=2 when nums = [1, 2]?

easy

A. [[], [1], [2]]

B. [[], [1], [1, 2], [2]]

C. [[], [1], [2], [1, 2], [2, 2]]

D. [[], [1], [2], [1, 2]]

Solution

1. Step 1: Trace result after processing num=1

   Initially result = [[]]. After num=1, new_subsets = [[1]], result = [[], [1]].

2. Step 2: Trace result after processing num=2

   For each subset in [[], [1]], add 2: new_subsets = [[2], [1, 2]]. Extend result: [[], [1], [2], [1, 2]].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All subsets of [1,2] are present exactly once [OK]

Hint: Iterative subsets double result size each iteration [OK]

Common Mistakes:

• Forgetting to add subsets with current num
• Appending duplicates
• Wrong order of subsets

3. What is the time complexity of the optimal backtracking solution for Combination Sum II with n candidates, considering sorting and pruning?

medium

A. O(n^2) due to nested loops and pruning

B. O(2^n * n) because each subset can be generated and copying path costs O(n)

C. O(n * target) similar to classic DP subset sum

D. O(n!) due to permutations of candidates

Solution

1. Step 1: Identify recursion tree size

   Backtracking explores subsets, up to 2^n subsets in worst case.

2. Step 2: Account for path copying cost

   Each valid combination copied costs O(n), so total time is O(2^n * n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Exponential subsets with path copying dominates [OK]

Hint: Backtracking subsets generate 2^n possibilities, each copied O(n) time [OK]

Common Mistakes:

• Confusing with DP O(n*target)
• Assuming pruning reduces to polynomial
• Thinking permutations cause factorial time

4. Identify the bug in the following code snippet that generates subsets iteratively:

medium

A. Modifying subsets in place without copying causes all subsets to be identical

B. Extending result inside the loop causes infinite loop

C. Starting result with [[]] misses the empty subset

D. Using append instead of extend on subsets is incorrect

Solution

1. Step 1: Analyze subset modification

   The code appends num directly to subsets in result, modifying them in place.

2. Step 2: Consequence of in-place modification

   All subsets in result end up referencing the same list, causing duplicates and incorrect subsets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct approach copies subsets before adding new elements [OK]

Hint: Always copy subsets before adding new elements [OK]

Common Mistakes:

• Modifying lists in place
• Extending result inside loop without fix
• Wrong initial result value

5. Suppose you want to generate all combinations of size k from numbers 1 to n, but now elements can be reused multiple times in a combination (combinations with replacement). Which modification to the backtracking approach correctly handles this?

hard

A. Use iterative lexicographic generation without any changes

B. Change the recursive call to backtrack(i + 1, path) to prevent reuse of elements

C. Change the recursive call to backtrack(i, path) to allow reuse of the current element

D. Sort the input array before backtracking to handle duplicates

Solution

1. Step 1: Understand combinations with replacement allow repeated elements

   To allow reuse, the recursive call must not increment start index beyond current element.

2. Step 2: Modify recursion to backtrack(i, path) to allow current element reuse

   This ensures the same element can be chosen multiple times in subsequent recursive calls.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Using backtrack(i, path) enables combinations with replacement [OK]

Hint: Reuse requires recursive calls with same start index [OK]

Common Mistakes:

• Incrementing start index prevents element reuse