Count of Subsets With Sum K

🎯

Count of Subsets With Sum K

mediumBACKTRACKINGAmazonGoogle

Imagine you have a collection of coins and want to find out how many different ways you can pick some coins so that their total value equals exactly a target amount.

💡 This problem asks us to count how many subsets of a given list sum up to a target value. Beginners often struggle because the number of subsets grows exponentially, and it's not obvious how to efficiently explore all possibilities without missing or double-counting subsets.

📋

Problem Statement

Given an array of integers and a target sum K, find the number of subsets of the array whose elements sum exactly to K. Return the count of such subsets.

1 ≤ n ≤ 10^5 (for optimized solutions)Array elements can be positive integers0 ≤ K ≤ sum of all elements

💡

Example

Input"arr = [1, 2, 3, 3], K = 6"

Output3

The subsets are [1,2,3], [3,3], and [1,2,3] (the second 3 is different element).

• Empty array with K=0 → 1 (empty subset counts)
• Array with all elements greater than K → 0
• Array with multiple zeros and K=0 → multiple subsets including empty and zeros
• Single element equal to K → 1

⚠️

Common Mistakes

Not handling empty subset sum correctly

Incorrect count when K=0, often missing the empty subset

✅ Initialize dp[0] = 1 or return 1 when index == len(arr) and current_sum == K

Using forward iteration in space optimized DP

Overcounts subsets by reusing updated dp values in the same iteration

✅ Iterate sums backward from K down to current element value

Not memoizing with both index and current_sum as key

Incorrect caching leads to wrong counts or missed subproblems

✅ Use a tuple or string key combining index and current_sum for memo

Assuming all elements are positive without checking constraints

DP approach fails or produces incorrect results if negative numbers present

✅ Clarify constraints or use different algorithms for negative numbers

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem deeply by exploring all subset combinations explicitly, even though it's inefficient for large inputs.

Intuition

Try every element: either include it in the subset or exclude it, and recursively count subsets that sum to K.

Algorithm

1. Start from the first element and current sum 0.
2. At each element, recursively explore two options: include it or exclude it.
3. If current sum equals K at the end of the array, increment count.
4. Return the total count from all recursive calls.

💡 The recursion tree grows exponentially, and it's easy to miss that each element has two choices, leading to 2^n subsets.

</>

Code

def count_subsets(arr, K, index=0, current_sum=0):
    if index == len(arr):
        return 1 if current_sum == K else 0
    # Include current element
    count_incl = count_subsets(arr, K, index + 1, current_sum + arr[index])
    # Exclude current element
    count_excl = count_subsets(arr, K, index + 1, current_sum)
    return count_incl + count_excl

# Driver code
if __name__ == '__main__':
    arr = [1, 2, 3, 3]
    K = 6
    print(count_subsets(arr, K))

Line Notes

def count_subsets(arr, K, index=0, current_sum=0):Defines recursive function with current index and sum to track subset progress

if index == len(arr):Base case: all elements considered

return 1 if current_sum == K else 0Count 1 if subset sum matches K, else 0

count_incl = count_subsets(arr, K, index + 1, current_sum + arr[index])Recurse including current element

count_excl = count_subsets(arr, K, index + 1, current_sum)Recurse excluding current element

return count_incl + count_exclSum counts from both choices

public class CountSubsets {
    public static int countSubsets(int[] arr, int K, int index, int currentSum) {
        if (index == arr.length) {
            return currentSum == K ? 1 : 0;
        }
        int countIncl = countSubsets(arr, K, index + 1, currentSum + arr[index]);
        int countExcl = countSubsets(arr, K, index + 1, currentSum);
        return countIncl + countExcl;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3};
        int K = 6;
        System.out.println(countSubsets(arr, K, 0, 0));
    }
}

Line Notes

public static int countSubsets(int[] arr, int K, int index, int currentSum)Recursive method with index and current sum parameters

if (index == arr.length)Base case: all elements processed

return currentSum == K ? 1 : 0;Return 1 if sum matches K, else 0

int countIncl = countSubsets(arr, K, index + 1, currentSum + arr[index]);Include current element in subset

int countExcl = countSubsets(arr, K, index + 1, currentSum);Exclude current element

return countIncl + countExcl;Add counts from both branches

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

int countSubsets(const vector<int>& arr, int K, int index = 0, int currentSum = 0) {
    if (index == arr.size()) {
        return currentSum == K ? 1 : 0;
    }
    int countIncl = countSubsets(arr, K, index + 1, currentSum + arr[index]);
    int countExcl = countSubsets(arr, K, index + 1, currentSum);
    return countIncl + countExcl;
}

int main() {
    vector<int> arr = {1, 2, 3, 3};
    int K = 6;
    cout << countSubsets(arr, K) << endl;
    return 0;
}

Line Notes

int countSubsets(const vector<int>& arr, int K, int index = 0, int currentSum = 0)Recursive function with default parameters for index and sum

if (index == arr.size())Base case: all elements considered

return currentSum == K ? 1 : 0;Return 1 if subset sum equals K, else 0

int countIncl = countSubsets(arr, K, index + 1, currentSum + arr[index]);Include current element in subset

int countExcl = countSubsets(arr, K, index + 1, currentSum);Exclude current element

return countIncl + countExcl;Sum counts from both recursive calls

function countSubsets(arr, K, index = 0, currentSum = 0) {
    if (index === arr.length) {
        return currentSum === K ? 1 : 0;
    }
    const countIncl = countSubsets(arr, K, index + 1, currentSum + arr[index]);
    const countExcl = countSubsets(arr, K, index + 1, currentSum);
    return countIncl + countExcl;
}

// Test
const arr = [1, 2, 3, 3];
const K = 6;
console.log(countSubsets(arr, K));

Line Notes

function countSubsets(arr, K, index = 0, currentSum = 0)Recursive function with default parameters for index and sum

if (index === arr.length)Base case: all elements processed

return currentSum === K ? 1 : 0;Return 1 if subset sum matches K, else 0

const countIncl = countSubsets(arr, K, index + 1, currentSum + arr[index]);Include current element in subset

const countExcl = countSubsets(arr, K, index + 1, currentSum);Exclude current element

return countIncl + countExcl;Add counts from both recursive branches

⏱

Complexity

TimeO(2^n)

SpaceO(n) due to recursion stack

Each element has two choices, leading to 2^n subsets. The recursion stack depth is n.

💡 For n=20, this means over a million recursive calls, which is too slow for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem and recursion structure.

🧠

Memoization (Top-Down DP)

💡 Memoization avoids recomputing the same subproblems by caching results, drastically improving efficiency over brute force.

Intuition

Store results of recursive calls keyed by current index and current sum to reuse them instead of recomputing.

Algorithm

1. Create a memo dictionary keyed by (index, current_sum).
2. Before recursive calls, check if result is cached; if yes, return it.
3. Otherwise, compute counts including and excluding current element.
4. Store and return the sum of counts.

💡 Memoization requires careful key design and understanding that overlapping subproblems exist.

</>

Code

def count_subsets_memo(arr, K, index=0, current_sum=0, memo=None):
    if memo is None:
        memo = {}
    if index == len(arr):
        return 1 if current_sum == K else 0
    if (index, current_sum) in memo:
        return memo[(index, current_sum)]
    count_incl = count_subsets_memo(arr, K, index + 1, current_sum + arr[index], memo)
    count_excl = count_subsets_memo(arr, K, index + 1, current_sum, memo)
    memo[(index, current_sum)] = count_incl + count_excl
    return memo[(index, current_sum)]

# Driver code
if __name__ == '__main__':
    arr = [1, 2, 3, 3]
    K = 6
    print(count_subsets_memo(arr, K))

Line Notes

memo = {}Initialize memo dictionary to cache results

if (index, current_sum) in memo:Check if subproblem already solved

memo[(index, current_sum)] = count_incl + count_exclStore computed result to avoid recomputation

return memo[(index, current_sum)]Return cached or newly computed result

import java.util.HashMap;
import java.util.Map;

public class CountSubsetsMemo {
    public static int countSubsets(int[] arr, int K, int index, int currentSum, Map<String, Integer> memo) {
        if (index == arr.length) {
            return currentSum == K ? 1 : 0;
        }
        String key = index + "," + currentSum;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        int countIncl = countSubsets(arr, K, index + 1, currentSum + arr[index], memo);
        int countExcl = countSubsets(arr, K, index + 1, currentSum, memo);
        memo.put(key, countIncl + countExcl);
        return memo.get(key);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3};
        int K = 6;
        Map<String, Integer> memo = new HashMap<>();
        System.out.println(countSubsets(arr, K, 0, 0, memo));
    }
}

Line Notes

public static int countSubsets(int[] arr, int K, int index, int currentSum, Map<String, Integer> memo)Recursive method with memo map passed as parameter to cache results

String key = index + "," + currentSum;Create unique key for current subproblem

if (memo.containsKey(key))Return cached result if available

memo.put(key, countIncl + countExcl);Store computed result in memo

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;

unordered_map<string, int> memo;

int countSubsets(const vector<int>& arr, int K, int index = 0, int currentSum = 0) {
    if (index == arr.size()) {
        return currentSum == K ? 1 : 0;
    }
    string key = to_string(index) + "," + to_string(currentSum);
    if (memo.find(key) != memo.end()) {
        return memo[key];
    }
    int countIncl = countSubsets(arr, K, index + 1, currentSum + arr[index]);
    int countExcl = countSubsets(arr, K, index + 1, currentSum);
    memo[key] = countIncl + countExcl;
    return memo[key];
}

int main() {
    vector<int> arr = {1, 2, 3, 3};
    int K = 6;
    cout << countSubsets(arr, K) << endl;
    return 0;
}

Line Notes

unordered_map<string, int> memo;Global memo map to store subproblem results

string key = to_string(index) + "," + to_string(currentSum);Create unique string key for memoization

if (memo.find(key) != memo.end())Return cached result if found

memo[key] = countIncl + countExcl;Cache computed result for reuse

const memo = new Map();
function countSubsets(arr, K, index = 0, currentSum = 0) {
    if (index === arr.length) {
        return currentSum === K ? 1 : 0;
    }
    const key = index + ',' + currentSum;
    if (memo.has(key)) {
        return memo.get(key);
    }
    const countIncl = countSubsets(arr, K, index + 1, currentSum + arr[index]);
    const countExcl = countSubsets(arr, K, index + 1, currentSum);
    memo.set(key, countIncl + countExcl);
    return memo.get(key);
}

// Test
const arr = [1, 2, 3, 3];
const K = 6;
console.log(countSubsets(arr, K));

Line Notes

const memo = new Map();Map to cache results of subproblems

const key = index + ',' + currentSum;Unique key for current subproblem

if (memo.has(key))Return cached result if available

memo.set(key, countIncl + countExcl);Store computed count in memo

⏱

Complexity

TimeO(n * K)

SpaceO(n * K) for memo storage and recursion stack

Memoization avoids recomputation by caching results for each index and sum combination, reducing exponential calls to polynomial.

💡 For n=20 and K=100, this means at most 2000 subproblems, which is much faster than brute force.

Interview Verdict: Accepted for moderate constraints

Memoization makes the solution efficient enough for moderate input sizes and is a common interview optimization.

🧠

Iterative DP (Bottom-Up Tabulation)

💡 Bottom-up DP builds the solution iteratively, which is often easier to debug and understand than recursion with memoization.

Intuition

Use a 2D boolean or integer DP table where dp[i][j] represents count of subsets from first i elements summing to j.

Algorithm

1. Initialize a 2D dp array of size (n+1) x (K+1) with zeros.
2. Set dp[0][0] = 1 since empty subset sums to 0.
3. Iterate over elements and sums, updating dp[i][j] by including or excluding current element.
4. Return dp[n][K] as the final count.

💡 The key is understanding how to build dp table using previous results and how to handle the base case.

</>

Code

def count_subsets_dp(arr, K):
    n = len(arr)
    dp = [[0] * (K + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        for j in range(K + 1):
            dp[i][j] = dp[i-1][j]
            if j >= arr[i-1]:
                dp[i][j] += dp[i-1][j - arr[i-1]]
    return dp[n][K]

# Driver code
if __name__ == '__main__':
    arr = [1, 2, 3, 3]
    K = 6
    print(count_subsets_dp(arr, K))

Line Notes

dp = [[0] * (K + 1) for _ in range(n + 1)]Create DP table with rows for elements and columns for sums

dp[0][0] = 1Empty subset sums to zero, so count is 1

dp[i][j] = dp[i-1][j]Count subsets excluding current element

if j >= arr[i-1]:Check if current element can be included

dp[i][j] += dp[i-1][j - arr[i-1]]Add count of subsets including current element

public class CountSubsetsDP {
    public static int countSubsets(int[] arr, int K) {
        int n = arr.length;
        int[][] dp = new int[n + 1][K + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= K; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= arr[i - 1]) {
                    dp[i][j] += dp[i - 1][j - arr[i - 1]];
                }
            }
        }
        return dp[n][K];
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3};
        int K = 6;
        System.out.println(countSubsets(arr, K));
    }
}

Line Notes

int[][] dp = new int[n + 1][K + 1];DP table to store counts for subsets and sums

dp[0][0] = 1;Base case: empty subset sums to zero

dp[i][j] = dp[i - 1][j];Count subsets excluding current element

if (j >= arr[i - 1])Check if current element can be included

dp[i][j] += dp[i - 1][j - arr[i - 1]];Add count including current element

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

int countSubsets(const vector<int>& arr, int K) {
    int n = arr.size();
    vector<vector<int>> dp(n + 1, vector<int>(K + 1, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= K; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= arr[i - 1]) {
                dp[i][j] += dp[i - 1][j - arr[i - 1]];
            }
        }
    }
    return dp[n][K];
}

int main() {
    vector<int> arr = {1, 2, 3, 3};
    int K = 6;
    cout << countSubsets(arr, K) << endl;
    return 0;
}

Line Notes

vector<vector<int>> dp(n + 1, vector<int>(K + 1, 0));Initialize DP table with zeros

dp[0][0] = 1;Empty subset sums to zero

dp[i][j] = dp[i - 1][j];Count subsets excluding current element

if (j >= arr[i - 1])Check if current element can be included

dp[i][j] += dp[i - 1][j - arr[i - 1]];Add count including current element

function countSubsets(arr, K) {
    const n = arr.length;
    const dp = Array.from({ length: n + 1 }, () => Array(K + 1).fill(0));
    dp[0][0] = 1;
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j <= K; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= arr[i - 1]) {
                dp[i][j] += dp[i - 1][j - arr[i - 1]];
            }
        }
    }
    return dp[n][K];
}

// Test
const arr = [1, 2, 3, 3];
const K = 6;
console.log(countSubsets(arr, K));

Line Notes

const dp = Array.from({ length: n + 1 }, () => Array(K + 1).fill(0));Create 2D DP array initialized to zero

dp[0][0] = 1;Base case: empty subset sums to zero

dp[i][j] = dp[i - 1][j];Count subsets excluding current element

if (j >= arr[i - 1])Check if current element can be included

dp[i][j] += dp[i - 1][j - arr[i - 1]];Add count including current element

⏱

Complexity

TimeO(n * K)

SpaceO(n * K)

We fill a table of size n by K, computing counts for each subproblem once.

💡 For n=20 and K=100, this means 2000 table entries, which is efficient and practical.

Interview Verdict: Accepted

This is the standard approach for counting subsets with sum K and is efficient for moderate constraints.

🧠

Space Optimized DP (1D Array)

💡 We can reduce space by using a 1D DP array since each row depends only on the previous row.

Intuition

Use a 1D array where dp[j] stores count of subsets summing to j so far, updating it in reverse to avoid overwriting needed values.

Algorithm

1. Initialize a 1D dp array of size K+1 with dp[0] = 1.
2. Iterate over each element in the array.
3. For each element, iterate sums from K down to element value.
4. Update dp[j] by adding dp[j - element] to count subsets including current element.
5. Return dp[K] as the final count.

💡 Updating backwards ensures we don't reuse updated values in the same iteration, preserving correctness.

</>

Code

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

# Driver code
if __name__ == '__main__':
    arr = [1, 2, 3, 3]
    K = 6
    print(count_subsets_space_optimized(arr, K))

Line Notes

dp = [0] * (K + 1)Initialize 1D DP array for sums

dp[0] = 1Empty subset sums to zero

for j in range(K, num - 1, -1)Iterate backwards to avoid overwriting needed values

dp[j] += dp[j - num]Add count of subsets including current element

public class CountSubsetsSpaceOpt {
    public static int countSubsets(int[] arr, int K) {
        int[] dp = new int[K + 1];
        dp[0] = 1;
        for (int num : arr) {
            for (int j = K; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[K];
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3};
        int K = 6;
        System.out.println(countSubsets(arr, K));
    }
}

Line Notes

int[] dp = new int[K + 1];1D DP array to store counts for sums

dp[0] = 1;Base case: empty subset sums to zero

for (int j = K; j >= num; j--)Iterate backwards to prevent using updated values in same iteration

dp[j] += dp[j - num];Add count including current element

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

int countSubsets(const vector<int>& arr, int K) {
    vector<int> dp(K + 1, 0);
    dp[0] = 1;
    for (int num : arr) {
        for (int j = K; j >= num; j--) {
            dp[j] += dp[j - num];
        }
    }
    return dp[K];
}

int main() {
    vector<int> arr = {1, 2, 3, 3};
    int K = 6;
    cout << countSubsets(arr, K) << endl;
    return 0;
}

Line Notes

vector<int> dp(K + 1, 0);1D DP vector initialized to zero

dp[0] = 1;Empty subset sums to zero

for (int j = K; j >= num; j--)Iterate backwards to avoid overwriting needed dp values

dp[j] += dp[j - num];Update count including current element

function countSubsets(arr, K) {
    const dp = Array(K + 1).fill(0);
    dp[0] = 1;
    for (const num of arr) {
        for (let j = K; j >= num; j--) {
            dp[j] += dp[j - num];
        }
    }
    return dp[K];
}

// Test
const arr = [1, 2, 3, 3];
const K = 6;
console.log(countSubsets(arr, K));

Line Notes

const dp = Array(K + 1).fill(0);Initialize 1D DP array for sums

dp[0] = 1;Empty subset sums to zero

for (let j = K; j >= num; j--)Iterate backwards to avoid using updated values prematurely

dp[j] += dp[j - num];Add count of subsets including current element

⏱

Complexity

TimeO(n * K)

SpaceO(K)

We use a single array of size K+1 and update it for each element, reducing space from O(n*K) to O(K).

💡 For large n and K, this saves memory and is the preferred approach in interviews.

Interview Verdict: Accepted

This is the optimal space solution for counting subsets with sum K and is often expected in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 For interviews, coding the space optimized DP is ideal, but understanding brute force and memoization is essential for explaining your thought process.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Memoization	O(n * K)	O(n * K) memo + O(n) stack	Possible but less than brute force	Yes	Good to explain optimization
3. Bottom-Up DP	O(n * K)	O(n * K)	No	Yes	Good to code if allowed
4. Space Optimized DP	O(n * K)	O(K)	No	No (without extra tracking)	Best to code in interviews

💼

Interview Strategy

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

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force recursive approach to show understanding of the problem.Step 3: Explain the inefficiency and introduce memoization to optimize.Step 4: Discuss bottom-up DP for iterative clarity and efficiency.Step 5: Finally, present space optimized DP as the best practical solution.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test & Optimize: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of recursion, memoization, DP table construction, and space optimization techniques.

Common Follow-ups

• What if array contains negative numbers? → DP approach needs modification or different technique.
• How to print all subsets instead of count? → Use backtracking with path tracking.

💡 These follow-ups test your ability to adapt the solution and extend it beyond counting.

🔍

Pattern Recognition

When to Use

1) Asked to count subsets/combinations with a sum or target, 2) Elements are positive integers, 3) Problem hints at include/exclude or subset sums, 4) Constraints allow DP or recursion.

Signature Phrases

count subsets with sumnumber of ways to reach targetsubset sum equals K

NOT This Pattern When

Problems asking for maximum/minimum sums or subsets without counting are different patterns.

Similar Problems

Subset Sum Problem - decision version of this counting problemPartition Equal Subset Sum - special case of sum K = total/2

Practice

1. You are given an array of integers and need to find the number of subsets whose bitwise OR equals the maximum possible OR value among all subsets. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach selecting elements with highest bits set first

B. Iterative bitmask enumeration generating all subsets and computing their OR

C. Dynamic programming based on subset sums

D. Sorting the array and using two pointers to find max OR subsets

Solution

1. Step 1: Understand the problem requires checking all subsets

   Since the maximum bitwise OR depends on any combination of elements, all subsets must be considered.

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

   Iterative bitmask enumeration systematically generates all subsets and computes their OR, ensuring no subset is missed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask enumeration covers all subsets -> optimal [OK]

Hint: Bitmask enumeration covers all subsets exhaustively [OK]

Common Mistakes:

• Assuming greedy selection suffices for max OR
• Confusing subset sum DP with bitwise OR problem

2. Consider the following Python code for finding the largest divisible subset. What is the final returned list when the input is [1, 2, 3]?

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:
                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]

print(largestDivisibleSubset([1, 2, 3]))

easy

A. [1, 2]

B. [1, 3]

C. [1, 2, 3]

D. [2, 3]

Solution

1. Step 1: Trace dp and prev arrays

   Sorted nums = [1, 2, 3]. For i=1 (2), dp[1]=2, prev[1]=0 since 2 % 1 == 0. For i=2 (3), dp[2]=2, prev[2]=0 since 3 % 1 == 0 but 3 % 2 != 0 (break early).

2. Step 2: Reconstruct subset from max_index=1 or 2

   dp[1] and dp[2] both 2, max_index updated to 2 last. Reconstruct: nums[2]=3, prev[2]=0 -> nums[0]=1. Result reversed is [1, 3].

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Subset [1,3] is largest divisible subset returned [OK]

Hint: Trace dp and prev arrays carefully [OK]

Common Mistakes:

• Assuming [1,2,3] all divisible chain without checking divisibility
• Confusing indices when reconstructing subset
• Ignoring early break in inner loop

3. You are given an integer array that may contain duplicates. Your task is to find all possible subsets without duplicate subsets in the result. Which approach guarantees generating all unique subsets efficiently without redundant computations?

easy

A. Generate all subsets using brute force recursion and then filter duplicates by storing subsets in a hash set.

B. Use a greedy algorithm that picks elements only if they are not duplicates of the previous element.

C. Use dynamic programming with a 2D table tracking subset sums to avoid duplicates.

D. Sort the array and use backtracking with skipping duplicates at the same recursion depth to avoid repeated subsets.

Solution

1. Step 1: Understand the problem constraints

   The problem requires generating all unique subsets from an array that may contain duplicates, avoiding duplicate subsets in the output.

2. Step 2: Identify the approach that handles duplicates efficiently

   Sorting the array groups duplicates together, allowing the backtracking algorithm to skip duplicates at the same recursion level, preventing repeated subsets without extra filtering.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking with sorting and skipping duplicates is the standard pattern for Subsets II [OK]

Hint: Sort and skip duplicates at recursion level [OK]

Common Mistakes:

• Using greedy approach misses some subsets
• DP approach is unrelated to subset generation here
• Brute force with set filtering is inefficient

4. Consider the following Python code that generates all subsets of nums = [1, 2, 3]. What is the value of subset when mask = 5 during the iteration?

easy

A. [1, 3]

B. [2, 3]

C. [1, 2]

D. [3]

Solution

1. Step 1: Convert mask=5 to binary

   5 in binary is 101, meaning bits 0 and 2 are set.

2. Step 2: Map bits to indices in nums

   Bit 0 corresponds to nums[0]=1, bit 2 corresponds to nums[2]=3, so subset = [1, 3].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mask 5 selects elements at positions 0 and 2 -> [1, 3] [OK]

Hint: Mask bits correspond to included elements [OK]

Common Mistakes:

• Off-by-one bit indexing
• Confusing mask bits with element values

5. The following code attempts to solve Combination Sum (Reuse Allowed). Identify the line containing the subtle bug that causes incorrect results or inefficiency:

def combinationSum(candidates, target):
    candidates.sort()
    result = []
    def backtrack(index, path, target):
        if target == 0:
            result.append(path[:])
            return
        if index == len(candidates) or target < 0:
            return
        max_use = target // candidates[index]
        for count in range(max_use + 1):
            path += [candidates[index]] * count
            backtrack(index + 1, path, target - candidates[index] * count)
            # Missing path restoration here
    backtrack(0, [], target)
    return result

medium

A. Line with 'path += [candidates[index]] * count' because path is modified without backtracking (pop).

B. Line with 'candidates.sort()' because sorting is unnecessary.

C. Line with 'if target == 0:' because it should check for target <= 0.

D. Line with 'max_use = target // candidates[index]' because integer division may cause errors.

Solution

1. Step 1: Analyze path modification in loop

   Path is extended by count copies of candidates[index] but never restored after recursive call, causing path to grow incorrectly across iterations.

2. Step 2: Identify missing backtracking step

   Proper backtracking requires removing added elements after recursion to restore path state for next iteration.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Modifying path without restoration leads to incorrect combinations [OK]

Hint: Always restore path after recursion in backtracking [OK]

Common Mistakes:

• Forgetting to pop elements after recursion
• Assuming path copy avoids mutation issues