Subset Sum

🎯

Subset Sum

mediumDPAmazonGoogleFacebook

Imagine you have a collection of coins and want to know if you can pick some to exactly pay a certain amount without breaking any coin.

💡 Subset Sum is a classic problem where you decide if a subset of numbers sums to a target. Beginners often struggle because the problem looks like a search problem but requires dynamic programming to solve efficiently.

📋

Problem Statement

Given an array of positive integers nums and a target sum S, determine if there exists a subset of nums whose sum is exactly S. Return true if such a subset exists, otherwise false.

1 ≤ n ≤ 10^51 ≤ nums[i] ≤ 10^41 ≤ S ≤ 10^6

💡

Example

Input"nums = [3, 34, 4, 12, 5, 2], S = 9"

Outputtrue

Subset [4, 5] sums to 9.

Input"nums = [1, 2, 3, 7], S = 6"

Outputtrue

Subset [1, 2, 3] sums to 6.

Input"nums = [1, 2, 7, 1, 5], S = 10"

Outputtrue

Subset [2, 7, 1] sums to 10.

Input"nums = [1, 3, 5, 9], S = 8"

Outputfalse

No subset sums to 8.

• Empty array with S=0 → true (empty subset)
• Empty array with S>0 → false (no elements to sum)
• All elements greater than S → false
• S equals sum of all elements → true

🔁

Why DP?

Why greedy fails:

Greedy fails because picking the largest number first may prevent reaching the exact sum. For example, nums=[3,5,7], S=10. Greedy picks 7 first, then cannot reach 10, but subset [3,7] sums to 10.

DP state:

dp[i][w] means whether it is possible to form sum w using the first i elements.

Recurrence:dp[i][w] = dp[i-1][w] OR dp[i-1][w - nums[i-1]] if w >= nums[i-1]

We can form sum w either by excluding the current element or including it if it fits.

⚠️

Common Mistakes

Not handling base case target=0 correctly

Function returns false even when empty subset sums to 0

✅ Explicitly return true when target == 0

Iterating sums forwards in space optimized DP

Overcounts elements, leading to incorrect true results

✅ Iterate sums backwards to avoid reusing updated states

Using memo keys incorrectly (e.g., only index without target)

Incorrect caching leads to wrong answers or missed subproblems

✅ Use both index and target as memo key

Not initializing dp[0][0] = True in tabulation

Algorithm fails to recognize empty subset sums to zero

✅ Set dp[i][0] = True for all i

Assuming greedy approach works

Fails on inputs where largest elements block exact sum

✅ Use DP instead of greedy

🧠

Brute Force (Pure Recursion)

💡 This approach is the foundation to understand the problem by exploring all subsets, but it is inefficient due to exponential time.

Intuition

Try all subsets by deciding for each element whether to include it or not, and check if any subset sums to target.

Algorithm

1. Start from the first element and target sum S.
2. Recursively try including the current element if it does not exceed the target.
3. Recursively try excluding the current element.
4. Return true if any recursive call finds a subset summing to S.

💡 The recursion tree grows exponentially because each element doubles the number of subsets.

Recurrence:f(i, w) = f(i-1, w) OR f(i-1, w - nums[i-1]) if w >= nums[i-1]

</>

Code

def subset_sum(nums, S):
    def dfs(i, target):
        if target == 0:
            return True
        if i == len(nums) or target < 0:
            return False
        # Include nums[i]
        include = dfs(i + 1, target - nums[i])
        # Exclude nums[i]
        exclude = dfs(i + 1, target)
        return include or exclude

    return dfs(0, S)

# Driver code
if __name__ == '__main__':
    nums = [3, 34, 4, 12, 5, 2]
    S = 9
    print(subset_sum(nums, S))  # True

Line Notes

def dfs(i, target):Defines recursive helper to explore subsets starting at index i

if target == 0:Base case: found subset summing exactly to target

if i == len(nums) or target < 0:Base case: no elements left or target overshot

include = dfs(i + 1, target - nums[i])Try including current element if possible

exclude = dfs(i + 1, target)Try excluding current element

return include or excludeReturn true if either choice leads to solution

public class SubsetSum {
    public static boolean subsetSum(int[] nums, int S) {
        return dfs(nums, 0, S);
    }

    private static boolean dfs(int[] nums, int i, int target) {
        if (target == 0) return true;
        if (i == nums.length || target < 0) return false;
        boolean include = dfs(nums, i + 1, target - nums[i]);
        boolean exclude = dfs(nums, i + 1, target);
        return include || exclude;
    }

    public static void main(String[] args) {
        int[] nums = {3, 34, 4, 12, 5, 2};
        int S = 9;
        System.out.println(subsetSum(nums, S)); // true
    }
}

Line Notes

public static boolean subsetSum(int[] nums, int S)Entry point calling recursive helper

if (target == 0) return true;Base case: subset found

if (i == nums.length || target < 0) return false;Base case: no more elements or target invalid

boolean include = dfs(nums, i + 1, target - nums[i]);Try including current element

boolean exclude = dfs(nums, i + 1, target);Try excluding current element

return include || exclude;Return true if either branch succeeds

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

bool dfs(const vector<int>& nums, int i, int target) {
    if (target == 0) return true;
    if (i == nums.size() || target < 0) return false;
    bool include = dfs(nums, i + 1, target - nums[i]);
    bool exclude = dfs(nums, i + 1, target);
    return include || exclude;
}

bool subsetSum(const vector<int>& nums, int S) {
    return dfs(nums, 0, S);
}

int main() {
    vector<int> nums = {3, 34, 4, 12, 5, 2};
    int S = 9;
    cout << (subsetSum(nums, S) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

bool dfs(const vector<int>& nums, int i, int target)Recursive helper exploring subsets from index i

if (target == 0) return true;Found subset summing to target

if (i == nums.size() || target < 0) return false;No elements left or invalid target

bool include = dfs(nums, i + 1, target - nums[i]);Include current element

bool exclude = dfs(nums, i + 1, target);Exclude current element

return include || exclude;Return true if either path works

function subsetSum(nums, S) {
    function dfs(i, target) {
        if (target === 0) return true;
        if (i === nums.length || target < 0) return false;
        let include = dfs(i + 1, target - nums[i]);
        let exclude = dfs(i + 1, target);
        return include || exclude;
    }
    return dfs(0, S);
}

// Test
console.log(subsetSum([3, 34, 4, 12, 5, 2], 9)); // true

Line Notes

function dfs(i, target)Recursive function to explore subsets starting at i

if (target === 0) return true;Base case: subset found

if (i === nums.length || target < 0) return false;No elements left or target invalid

let include = dfs(i + 1, target - nums[i]);Try including current element

let exclude = dfs(i + 1, target);Try excluding current element

return include || exclude;Return true if either branch succeeds

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack

Each element branches into two choices, doubling calls each time.

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

Interview Verdict: TLE

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

🧠

Top-Down Memoization

💡 Memoization caches results of subproblems to avoid recomputation, drastically improving efficiency over brute force.

Intuition

Store results of recursive calls for each index and target to reuse them instead of recomputing.

Algorithm

1. Initialize a memo dictionary to store results for (index, target).
2. Recursively explore including or excluding current element.
3. Before recursion, check if result is cached and return if so.
4. Return true if any path leads to target sum.

💡 Memoization prunes the recursion tree by remembering past results.

Recurrence:f(i, w) = f(i-1, w) OR f(i-1, w - nums[i-1]) if w >= nums[i-1]

</>

Code

def subset_sum(nums, S):
    memo = {}
    def dfs(i, target):
        if target == 0:
            return True
        if i == len(nums) or target < 0:
            return False
        if (i, target) in memo:
            return memo[(i, target)]
        include = dfs(i + 1, target - nums[i])
        exclude = dfs(i + 1, target)
        memo[(i, target)] = include or exclude
        return memo[(i, target)]

    return dfs(0, S)

# Driver code
if __name__ == '__main__':
    nums = [3, 34, 4, 12, 5, 2]
    S = 9
    print(subset_sum(nums, S))  # True

Line Notes

memo = {}Initialize cache to store results of subproblems

if (i, target) in memo:Return cached result if available to avoid recomputation

memo[(i, target)] = include or excludeStore result of current subproblem

return memo[(i, target)]Return cached or computed result

import java.util.*;
public class SubsetSum {
    static Map<String, Boolean> memo = new HashMap<>();

    public static boolean subsetSum(int[] nums, int S) {
        memo.clear();
        return dfs(nums, 0, S);
    }

    private static boolean dfs(int[] nums, int i, int target) {
        if (target == 0) return true;
        if (i == nums.length || target < 0) return false;
        String key = i + "," + target;
        if (memo.containsKey(key)) return memo.get(key);
        boolean include = dfs(nums, i + 1, target - nums[i]);
        boolean exclude = dfs(nums, i + 1, target);
        memo.put(key, include || exclude);
        return memo.get(key);
    }

    public static void main(String[] args) {
        int[] nums = {3, 34, 4, 12, 5, 2};
        int S = 9;
        System.out.println(subsetSum(nums, S)); // true
    }
}

Line Notes

static Map<String, Boolean> memo = new HashMap<>();Cache to store subproblem results

String key = i + "," + target;Create unique key for memoization

if (memo.containsKey(key)) return memo.get(key);Return cached result if present

memo.put(key, include || exclude);Store computed result

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

unordered_map<string, bool> memo;

string makeKey(int i, int target) {
    return to_string(i) + "," + to_string(target);
}

bool dfs(const vector<int>& nums, int i, int target) {
    if (target == 0) return true;
    if (i == nums.size() || target < 0) return false;
    string key = makeKey(i, target);
    if (memo.find(key) != memo.end()) return memo[key];
    bool include = dfs(nums, i + 1, target - nums[i]);
    bool exclude = dfs(nums, i + 1, target);
    memo[key] = include || exclude;
    return memo[key];
}

bool subsetSum(const vector<int>& nums, int S) {
    memo.clear();
    return dfs(nums, 0, S);
}

int main() {
    vector<int> nums = {3, 34, 4, 12, 5, 2};
    int S = 9;
    cout << (subsetSum(nums, S) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

unordered_map<string, bool> memo;Cache for storing subproblem results

string key = makeKey(i, target);Generate unique key for memo

if (memo.find(key) != memo.end()) return memo[key];Return cached result if found

memo[key] = include || exclude;Store computed result

function subsetSum(nums, S) {
    const memo = new Map();
    function dfs(i, target) {
        if (target === 0) return true;
        if (i === nums.length || target < 0) return false;
        const key = i + ',' + target;
        if (memo.has(key)) return memo.get(key);
        const include = dfs(i + 1, target - nums[i]);
        const exclude = dfs(i + 1, target);
        memo.set(key, include || exclude);
        return memo.get(key);
    }
    return dfs(0, S);
}

// Test
console.log(subsetSum([3, 34, 4, 12, 5, 2], 9)); // true

Line Notes

const memo = new Map();Initialize cache for memoization

const key = i + ',' + target;Create unique key for current state

if (memo.has(key)) return memo.get(key);Return cached result if available

memo.set(key, include || exclude);Store computed result

⏱

Complexity

TimeO(n * S)

SpaceO(n * S) for memo and recursion stack

Each subproblem (i, target) is computed once and cached.

💡 For n=20 and S=1000, this reduces calls from millions to about 20,000.

Interview Verdict: Accepted

Efficient enough for moderate constraints and a common interview solution.

🧠

Bottom-Up Tabulation

💡 Tabulation builds the solution iteratively from smaller subproblems, avoiding recursion and improving clarity and performance.

Intuition

Create a 2D boolean DP table where dp[i][w] indicates if sum w can be formed using first i elements.

Algorithm

1. Initialize dp array with dp[0][0] = True (sum 0 with 0 elements).
2. Iterate over elements and sums, updating dp[i][w] based on inclusion/exclusion.
3. If dp[n][S] is True, subset exists.
4. Return dp[n][S].

💡 This approach systematically builds all possible sums using subsets of elements.

Recurrence:dp[i][w] = dp[i-1][w] OR dp[i-1][w - nums[i-1]] if w >= nums[i-1]

</>

Code

def subset_sum(nums, S):
    n = len(nums)
    dp = [[False] * (S + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = True
    for i in range(1, n + 1):
        for w in range(1, S + 1):
            if nums[i - 1] <= w:
                dp[i][w] = dp[i - 1][w] or dp[i - 1][w - nums[i - 1]]
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][S]

# Driver code
if __name__ == '__main__':
    nums = [3, 34, 4, 12, 5, 2]
    S = 9
    print(subset_sum(nums, S))  # True

Line Notes

dp = [[False] * (S + 1) for _ in range(n + 1)]Create DP table with n+1 rows and S+1 columns

for i in range(n + 1): dp[i][0] = TrueSum 0 is always possible with empty subset

for i in range(1, n + 1):Iterate over elements

for w in range(1, S + 1):Iterate over all sums up to S

if nums[i - 1] <= w:Check if current element can be included

dp[i][w] = dp[i - 1][w] or dp[i - 1][w - nums[i - 1]]Include or exclude current element

else: dp[i][w] = dp[i - 1][w]Cannot include current element, inherit previous state

public class SubsetSum {
    public static boolean subsetSum(int[] nums, int S) {
        int n = nums.length;
        boolean[][] dp = new boolean[n + 1][S + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= S; w++) {
                if (nums[i - 1] <= w) {
                    dp[i][w] = dp[i - 1][w] || dp[i - 1][w - nums[i - 1]];
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        return dp[n][S];
    }

    public static void main(String[] args) {
        int[] nums = {3, 34, 4, 12, 5, 2};
        int S = 9;
        System.out.println(subsetSum(nums, S)); // true
    }
}

Line Notes

boolean[][] dp = new boolean[n + 1][S + 1];DP table for sums and elements

for (int i = 0; i <= n; i++) dp[i][0] = true;Sum 0 achievable with empty subset

for (int i = 1; i <= n; i++)Iterate over elements

for (int w = 1; w <= S; w++)Iterate over sums

if (nums[i - 1] <= w)Check if current element fits in sum

dp[i][w] = dp[i - 1][w] || dp[i - 1][w - nums[i - 1]];Include or exclude element

else dp[i][w] = dp[i - 1][w];Exclude element if too large

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

bool subsetSum(const vector<int>& nums, int S) {
    int n = nums.size();
    vector<vector<bool>> dp(n + 1, vector<bool>(S + 1, false));
    for (int i = 0; i <= n; i++) dp[i][0] = true;
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= S; w++) {
            if (nums[i - 1] <= w) {
                dp[i][w] = dp[i - 1][w] || dp[i - 1][w - nums[i - 1]];
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][S];
}

int main() {
    vector<int> nums = {3, 34, 4, 12, 5, 2};
    int S = 9;
    cout << (subsetSum(nums, S) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

vector<vector<bool>> dp(n + 1, vector<bool>(S + 1, false));Initialize DP table

for (int i = 0; i <= n; i++) dp[i][0] = true;Sum 0 is always possible

for (int i = 1; i <= n; i++)Iterate over elements

for (int w = 1; w <= S; w++)Iterate over sums

if (nums[i - 1] <= w)Check if current element can be included

dp[i][w] = dp[i - 1][w] || dp[i - 1][w - nums[i - 1]];Include or exclude element

else dp[i][w] = dp[i - 1][w];Exclude element if too large

function subsetSum(nums, S) {
    const n = nums.length;
    const dp = Array.from({ length: n + 1 }, () => Array(S + 1).fill(false));
    for (let i = 0; i <= n; i++) dp[i][0] = true;
    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= S; w++) {
            if (nums[i - 1] <= w) {
                dp[i][w] = dp[i - 1][w] || dp[i - 1][w - nums[i - 1]];
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][S];
}

// Test
console.log(subsetSum([3, 34, 4, 12, 5, 2], 9)); // true

Line Notes

const dp = Array.from({ length: n + 1 }, () => Array(S + 1).fill(false));Create DP table

for (let i = 0; i <= n; i++) dp[i][0] = true;Sum 0 achievable with empty subset

for (let i = 1; i <= n; i++)Iterate over elements

for (let w = 1; w <= S; w++)Iterate over sums

if (nums[i - 1] <= w)Check if element fits in sum

dp[i][w] = dp[i - 1][w] || dp[i - 1][w - nums[i - 1]];Include or exclude element

else dp[i][w] = dp[i - 1][w];Exclude element if too large

⏱

Complexity

TimeO(n * S)

SpaceO(n * S)

We fill a table of size n by S once.

💡 For n=20 and S=1000, this means 20,000 operations, which is efficient.

Interview Verdict: Accepted

This is the standard DP solution for subset sum and is optimal for moderate constraints.

🧠

Space Optimized Bottom-Up

💡 We can reduce space from O(n*S) to O(S) by using a single array and iterating sums backwards.

Intuition

Use a 1D dp array where dp[w] means if sum w is achievable so far, updating it for each element.

Algorithm

1. Initialize dp array of size S+1 with False, set dp[0] = True.
2. For each element, iterate sums from S down to element value.
3. Update dp[w] = dp[w] OR dp[w - element].
4. Return dp[S] indicating if sum S is achievable.

💡 Backward iteration prevents counting an element multiple times in one pass.

Recurrence:dp[w] = dp[w] OR dp[w - nums[i]] if w >= nums[i]

</>

Code

def subset_sum(nums, S):
    dp = [False] * (S + 1)
    dp[0] = True
    for num in nums:
        for w in range(S, num - 1, -1):
            dp[w] = dp[w] or dp[w - num]
    return dp[S]

# Driver code
if __name__ == '__main__':
    nums = [3, 34, 4, 12, 5, 2]
    S = 9
    print(subset_sum(nums, S))  # True

Line Notes

dp = [False] * (S + 1)Initialize 1D DP array for sums

dp[0] = TrueSum 0 is always achievable

for num in nums:Iterate over each element

for w in range(S, num - 1, -1):Iterate sums backwards to avoid reuse

dp[w] = dp[w] or dp[w - num]Update dp[w] if sum w can be formed

public class SubsetSum {
    public static boolean subsetSum(int[] nums, int S) {
        boolean[] dp = new boolean[S + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int w = S; w >= num; w--) {
                dp[w] = dp[w] || dp[w - num];
            }
        }
        return dp[S];
    }

    public static void main(String[] args) {
        int[] nums = {3, 34, 4, 12, 5, 2};
        int S = 9;
        System.out.println(subsetSum(nums, S)); // true
    }
}

Line Notes

boolean[] dp = new boolean[S + 1];1D DP array for sums

dp[0] = true;Sum 0 achievable without elements

for (int num : nums)Iterate over elements

for (int w = S; w >= num; w--)Iterate sums backwards to avoid reuse

dp[w] = dp[w] || dp[w - num];Update dp[w] if sum w achievable

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

bool subsetSum(const vector<int>& nums, int S) {
    vector<bool> dp(S + 1, false);
    dp[0] = true;
    for (int num : nums) {
        for (int w = S; w >= num; w--) {
            dp[w] = dp[w] || dp[w - num];
        }
    }
    return dp[S];
}

int main() {
    vector<int> nums = {3, 34, 4, 12, 5, 2};
    int S = 9;
    cout << (subsetSum(nums, S) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

vector<bool> dp(S + 1, false);Initialize 1D DP array

dp[0] = true;Sum 0 achievable by empty subset

for (int num : nums)Iterate over elements

for (int w = S; w >= num; w--)Iterate sums backwards to avoid reuse

dp[w] = dp[w] || dp[w - num];Update dp[w] if sum w achievable

function subsetSum(nums, S) {
    const dp = Array(S + 1).fill(false);
    dp[0] = true;
    for (const num of nums) {
        for (let w = S; w >= num; w--) {
            dp[w] = dp[w] || dp[w - num];
        }
    }
    return dp[S];
}

// Test
console.log(subsetSum([3, 34, 4, 12, 5, 2], 9)); // true

Line Notes

const dp = Array(S + 1).fill(false);Initialize 1D DP array

dp[0] = true;Sum 0 achievable by empty subset

for (const num of nums)Iterate over elements

for (let w = S; w >= num; w--)Iterate sums backwards to avoid reuse

dp[w] = dp[w] || dp[w - num];Update dp[w] if sum w achievable

⏱

Complexity

TimeO(n * S)

SpaceO(S)

We use a single array updated for each element.

💡 This reduces memory usage significantly while maintaining speed.

Interview Verdict: Accepted

This is the most efficient practical solution for large inputs.

📊

All Approaches - One-Glance Tradeoffs

💡 Space optimized DP is preferred in 95% of interviews for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes (via recursion path)	Mention only - never code
2. Top-Down Memoization	O(n * S)	O(n * S)	Possible for large n	Yes (track memo states)	Good for explaining optimization
3. Bottom-Up Tabulation	O(n * S)	O(n * S)	No	Yes (track dp table)	Standard DP solution
4. Space Optimized Bottom-Up	O(n * S)	O(S)	No	No (without extra tracking)	Best practical solution

💼

Interview Strategy

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

How to Present

Clarify problem constraints and inputs.Explain brute force approach and its exponential complexity.Introduce memoization to optimize overlapping subproblems.Present bottom-up tabulation for iterative clarity.Show space optimization to demonstrate mastery.

Time Allocation

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

What the Interviewer Tests

Understanding of recursion, memoization, DP table construction, and space optimization.

Common Follow-ups

• What if negative numbers are allowed? → Use offset or different DP approach.
• How to find the subset itself? → Track choices in DP table and reconstruct.

💡 These follow-ups test deeper understanding and ability to extend solutions.

🔍

Pattern Recognition

When to Use

1) Problem asks if subset sums to target; 2) Elements are positive integers; 3) Need boolean answer; 4) Constraints allow DP

Signature Phrases

subset sums toexact sumchoose elements to reach target

NOT This Pattern When

Problems asking for maximum sum under capacity (0/1 knapsack with values), or unbounded knapsack

Similar Problems

Partition Equal Subset Sum - checks if array can be split into two equal sum subsetsTarget Sum - counts ways to assign + or - to reach target sum

Practice

1. You need to split a positive integer n into at least two positive integers such that the product of these integers is maximized. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Pure brute force recursion exploring all partitions without memoization

B. A greedy approach that always cuts the integer into 3s and 2s

C. Dynamic programming using bottom-up tabulation with state representing maximum product for each integer up to n

D. Divide and conquer by splitting the integer into two halves recursively without caching results

Solution

1. Step 1: Understand problem structure

   The problem requires maximizing product by splitting an integer into parts, which naturally fits a DP approach where subproblems represent maximum product for smaller integers.

2. Step 2: Evaluate options

   Greedy (always cutting 3s) fails on some inputs; brute force recursion is correct but inefficient; divide and conquer without memoization repeats work. Bottom-up DP tabulation efficiently computes all subproblems and combines results.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP tabulation ensures optimal substructure and overlapping subproblems [OK]

Hint: DP tabulation handles overlapping subproblems optimally [OK]

Common Mistakes:

• Believing greedy always works for integer break
• Ignoring memoization in recursion

2. You are given a list of jobs where each job has a start time, an end time, and a profit. You want to schedule jobs to maximize total profit such that no two jobs overlap. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming with jobs sorted by end time and binary search to find compatible jobs

B. Pure brute force recursion checking all subsets of jobs

C. Greedy algorithm that always picks the job with the earliest end time

D. Dynamic programming based on sorting jobs by start time and using prefix sums

Solution

1. Step 1: Understand job scheduling constraints

   The problem requires selecting non-overlapping jobs to maximize profit, which is a classic weighted interval scheduling problem.

2. Step 2: Identify the optimal approach

   Sorting jobs by end time allows binary searching for the last compatible job, enabling a DP solution that builds optimal profit incrementally.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy fails on overlapping jobs with higher profit; DP with binary search handles all cases optimally [OK]

Hint: Sort by end time and use DP with binary search [OK]

Common Mistakes:

• Assuming greedy by earliest end time always works
• Sorting by start time only
• Trying brute force without pruning

3. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the Equal Partition problem, where n is the number of elements and target is half the total sum?

medium

A. O(2^n) because the problem explores all subsets in worst case

B. O(n * n) because we iterate over all elements and all sums up to n

C. O(target^2) because the dp array size is target and we update it multiple times

D. O(n * target) because for each element we iterate over sums up to target

Solution

1. Step 1: Identify loops in the code

   The outer loop runs n times (for each element), and the inner loop runs up to target times (half the total sum).

2. Step 2: Calculate total time complexity

   Multiplying these gives O(n * target). The dp array updates are constant time per iteration.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Time depends on number of elements and target sum, not n squared or exponential [OK]

Hint: Time depends on n and target sum, not just n [OK]

Common Mistakes:

• Confusing n with target or assuming quadratic in n
• Forgetting target can be large

4. What is the time complexity of the optimal bottom-up dynamic programming solution for the problem, given strs has length l, and the constraints are m zeros and n ones?

medium

A. O(l * (m + n))

B. O(l * m * n)

C. O(l * m * n * max_length_of_string)

D. O(2^l)

Solution

1. Step 1: Identify loops in the code

   Outer loop iterates over all strings (l), inner loops iterate over m and n capacities.

2. Step 2: Calculate total operations

   Each string causes updates over a 2D dp array of size (m+1)*(n+1), so total complexity is O(l * m * n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Nested loops over l, m, n -> O(l * m * n) [OK]

Hint: Nested loops over strings and both capacities multiply complexities [OK]

Common Mistakes:

• Confusing sum with product of m and n
• Including string length in complexity unnecessarily

5. Suppose the problem is modified so that each element in the array can be used multiple times (unlimited reuse) to form k equal sum subsets. Which of the following modifications to the DP with bitmask tabulation approach correctly adapts to this change?

hard

A. Use backtracking with memoization on subsets but do not use bitmasking since reuse breaks subset uniqueness

B. Keep the same bitmask DP but allow setting dp[next_mask] multiple times without restriction

C. Replace bitmask DP with a classic unbounded knapsack DP that tracks sums without bitmasking

D. Modify the bitmask DP to reset dp states after each full subset sum is reached to allow reuse

Solution

1. Step 1: Understand reuse impact

   Allowing unlimited reuse breaks the uniqueness assumption of subsets represented by bitmasks.

2. Step 2: Identify suitable DP approach

   Classic unbounded knapsack DP tracks sums without bitmasking, correctly handling reuse.

3. Step 3: Evaluate other options

   Bitmask DP relies on unique element usage; modifying it without removing bitmasking leads to incorrect states.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Unbounded knapsack DP handles reuse correctly [OK]

Hint: Bitmask DP assumes unique usage; reuse needs unbounded knapsack DP [OK]

Common Mistakes:

• Trying to reuse bitmask DP without removing uniqueness assumption
• Ignoring that reuse breaks subset partitioning logic