Integer Break

🎯

Integer Break

mediumDPGoogleMicrosoft

Imagine you have a rope of length n and want to cut it into integer lengths to maximize the product of those lengths. How should you cut it?

💡 This problem is a classic example of dynamic programming where the goal is to maximize a product by breaking a number into parts. Beginners often struggle because the problem looks like a math puzzle but requires careful state definition and optimization.

📋

Problem Statement

Given an integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

2 ≤ n ≤ 10^5

💡

Example

Input"n = 10"

Output36

10 can be broken into 3 + 3 + 4, and 3*3*4 = 36 is the maximum product.

• n = 2 → output: 1 (only 1+1 possible)
• n = 3 → output: 2 (1+2 or 2+1, product 2)
• n = 4 → output: 4 (2+2, product 4)
• n = 58 → output: 1549681956 (large input to test efficiency)

🔁

Why DP?

Why greedy fails:

Greedy approach fails because always cutting the largest piece (like 3) does not guarantee maximum product for all n. For example, n=10: greedy might pick 3 repeatedly but missing the optimal combination 3+3+4.

DP state:

dp[i] represents the maximum product obtainable by breaking integer i into at least two positive integers.

Recurrence:dp[i] = max over j in [1, i-1] of max(j, dp[j]) * max(i-j, dp[i-j])

For each i, try breaking it into two parts j and i-j, and take the maximum product considering whether to break further or not.

⚠️

Common Mistakes

Not considering the case of not breaking a segment further (using max(j, dp[j]))

Incorrect product calculation, underestimating max product

✅ Always compare the segment length itself with its dp value

Forgetting base case dp[1] = 1

Recursion or dp fails or returns zero

✅ Initialize dp[1] = 1 explicitly

Using dp array of size n instead of n+1, causing index errors

Runtime errors or incorrect results

✅ Allocate dp array with size n+1 to include dp[n]

Trying to use greedy approach (always cut 3) without DP

Fails on some inputs, producing suboptimal results

✅ Use DP to consider all splits systematically

Not testing small inputs like n=2 or n=3

Code may fail or produce wrong output on edge cases

✅ Always test minimal inputs explicitly

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive structure and why naive recursion is inefficient due to repeated calculations.

Intuition

Try every possible first cut and recursively compute the maximum product for the remaining length, then take the best among all.

Algorithm

1. If n is 1, return 1 since it cannot be broken further.
2. For each possible first cut j from 1 to n-1:
3. Recursively compute max product for j and n-j.
4. Return the maximum product found among all cuts.

💡 The recursion explores all ways to break the integer, but it repeats calculations for the same subproblems multiple times.

Recurrence:f(n) = max_{1 ≤ j < n} (max(j, f(j)) * max(n-j, f(n-j)))

</>

Code

def integer_break(n):
    if n == 1:
        return 1
    max_product = 0
    for j in range(1, n):
        left = max(j, integer_break(j))
        right = max(n - j, integer_break(n - j))
        max_product = max(max_product, left * right)
    return max_product

# Driver code
if __name__ == '__main__':
    print(integer_break(10))  # Expected output: 36

Line Notes

if n == 1:Base case: cannot break further, product is 1

for j in range(1, n):Try every possible first cut position

left = max(j, integer_break(j))Decide whether to break j further or not

max_product = max(max_product, left * right)Update max product with current cut's product

public class IntegerBreak {
    public static int integerBreak(int n) {
        if (n == 1) return 1;
        int maxProduct = 0;
        for (int j = 1; j < n; j++) {
            int left = Math.max(j, integerBreak(j));
            int right = Math.max(n - j, integerBreak(n - j));
            maxProduct = Math.max(maxProduct, left * right);
        }
        return maxProduct;
    }

    public static void main(String[] args) {
        System.out.println(integerBreak(10)); // Expected output: 36
    }
}

Line Notes

if (n == 1) return 1;Base case to stop recursion

for (int j = 1; j < n; j++) {Try all possible cuts

int left = Math.max(j, integerBreak(j));Choose to break or not break left part

maxProduct = Math.max(maxProduct, left * right);Keep track of max product

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

int integerBreak(int n) {
    if (n == 1) return 1;
    int maxProduct = 0;
    for (int j = 1; j < n; j++) {
        int left = max(j, integerBreak(j));
        int right = max(n - j, integerBreak(n - j));
        maxProduct = max(maxProduct, left * right);
    }
    return maxProduct;
}

int main() {
    cout << integerBreak(10) << endl; // Expected output: 36
    return 0;
}

Line Notes

if (n == 1) return 1;Base case to prevent infinite recursion

for (int j = 1; j < n; j++) {Try all possible first cuts

int left = max(j, integerBreak(j));Decide to break or not break left segment

maxProduct = max(maxProduct, left * right);Update maximum product found

function integerBreak(n) {
    if (n === 1) return 1;
    let maxProduct = 0;
    for (let j = 1; j < n; j++) {
        let left = Math.max(j, integerBreak(j));
        let right = Math.max(n - j, integerBreak(n - j));
        maxProduct = Math.max(maxProduct, left * right);
    }
    return maxProduct;
}

// Test
console.log(integerBreak(10)); // Expected output: 36

Line Notes

if (n === 1) return 1;Stop recursion at smallest integer

for (let j = 1; j < n; j++) {Try every possible cut

let left = Math.max(j, integerBreak(j));Choose best product for left part

maxProduct = Math.max(maxProduct, left * right);Keep track of best product

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack

Each call branches into two recursive calls for smaller integers, leading to exponential 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's recursive nature.

🧠

Top-Down Memoization

💡 Memoization avoids repeated calculations by caching results, making the recursive solution efficient and practical.

Intuition

Store results of subproblems so that each integer's maximum product is computed once and reused.

Algorithm

1. Initialize a cache (dp array) to store maximum products for integers.
2. If the result for n is cached, return it.
3. Otherwise, compute max product by trying all cuts recursively.
4. Store and return the computed result.

💡 Memoization transforms exponential recursion into polynomial time by avoiding duplicate work.

Recurrence:f(n) = max_{1 ≤ j < n} (max(j, f(j)) * max(n-j, f(n-j)))

</>

Code

def integer_break(n, dp=None):
    if dp is None:
        dp = [-1] * (n + 1)
    if n == 1:
        return 1
    if dp[n] != -1:
        return dp[n]
    max_product = 0
    for j in range(1, n):
        left = max(j, integer_break(j, dp))
        right = max(n - j, integer_break(n - j, dp))
        max_product = max(max_product, left * right)
    dp[n] = max_product
    return max_product

# Driver code
if __name__ == '__main__':
    print(integer_break(10))  # Expected output: 36

Line Notes

dp = [-1] * (n + 1)Initialize cache with -1 indicating uncomputed

if dp[n] != -1:Return cached result if available

dp[n] = max_productStore computed result to avoid recomputation

for j in range(1, n):Try all cuts to find max product

import java.util.Arrays;

public class IntegerBreak {
    public static int integerBreak(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, -1);
        return helper(n, dp);
    }

    private static int helper(int n, int[] dp) {
        if (n == 1) return 1;
        if (dp[n] != -1) return dp[n];
        int maxProduct = 0;
        for (int j = 1; j < n; j++) {
            int left = Math.max(j, helper(j, dp));
            int right = Math.max(n - j, helper(n - j, dp));
            maxProduct = Math.max(maxProduct, left * right);
        }
        dp[n] = maxProduct;
        return maxProduct;
    }

    public static void main(String[] args) {
        System.out.println(integerBreak(10)); // Expected output: 36
    }
}

Line Notes

Arrays.fill(dp, -1);Mark all dp entries as uncomputed

if (dp[n] != -1) return dp[n];Return cached result if computed

dp[n] = maxProduct;Cache the computed max product

for (int j = 1; j < n; j++) {Try all possible cuts

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

int integerBreakHelper(int n, vector<int>& dp) {
    if (n == 1) return 1;
    if (dp[n] != -1) return dp[n];
    int maxProduct = 0;
    for (int j = 1; j < n; j++) {
        int left = max(j, integerBreakHelper(j, dp));
        int right = max(n - j, integerBreakHelper(n - j, dp));
        maxProduct = max(maxProduct, left * right);
    }
    dp[n] = maxProduct;
    return maxProduct;
}

int integerBreak(int n) {
    vector<int> dp(n + 1, -1);
    return integerBreakHelper(n, dp);
}

int main() {
    cout << integerBreak(10) << endl; // Expected output: 36
    return 0;
}

Line Notes

vector<int> dp(n + 1, -1);Initialize dp cache with -1

if (dp[n] != -1) return dp[n];Return cached result if available

dp[n] = maxProduct;Store computed result

for (int j = 1; j < n; j++) {Try all cuts to find max product

function integerBreak(n, dp = null) {
    if (dp === null) dp = new Array(n + 1).fill(-1);
    if (n === 1) return 1;
    if (dp[n] !== -1) return dp[n];
    let maxProduct = 0;
    for (let j = 1; j < n; j++) {
        let left = Math.max(j, integerBreak(j, dp));
        let right = Math.max(n - j, integerBreak(n - j, dp));
        maxProduct = Math.max(maxProduct, left * right);
    }
    dp[n] = maxProduct;
    return maxProduct;
}

// Test
console.log(integerBreak(10)); // Expected output: 36

Line Notes

if (dp === null) dp = new Array(n + 1).fill(-1);Initialize memo array once

if (dp[n] !== -1) return dp[n];Return cached result if computed

dp[n] = maxProduct;Cache computed max product

for (let j = 1; j < n; j++) {Try all possible cuts

⏱

Complexity

TimeO(n^2)

SpaceO(n) for dp array and recursion stack

Each integer up to n is computed once, and for each, we try all cuts up to n, resulting in quadratic time.

💡 For n=1000, this means about 1 million operations, which is efficient enough for interviews.

Interview Verdict: Accepted

Memoization makes the solution efficient and practical for large inputs.

🧠

Bottom-Up Tabulation

💡 Tabulation builds the solution from the smallest subproblems up to n, avoiding recursion and making the flow easier to understand and debug.

Intuition

Iteratively compute maximum product for all integers from 1 to n using previously computed results.

Algorithm

1. Initialize dp array with dp[1] = 1.
2. For each integer i from 2 to n:
3. Try all cuts j from 1 to i-1 and update dp[i] with max product.
4. Return dp[n] as the final answer.

💡 This approach ensures no recursion overhead and clearly shows how solutions build on smaller subproblems.

Recurrence:dp[i] = max_{1 ≤ j < i} (max(j, dp[j]) * max(i-j, dp[i-j]))

</>

Code

def integer_break(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        max_product = 0
        for j in range(1, i):
            left = max(j, dp[j])
            right = max(i - j, dp[i - j])
            max_product = max(max_product, left * right)
        dp[i] = max_product
    return dp[n]

# Driver code
if __name__ == '__main__':
    print(integer_break(10))  # Expected output: 36

Line Notes

dp = [0] * (n + 1)Initialize dp array to store max products

dp[1] = 1Base case: product for 1 is 1

for i in range(2, n + 1):Compute dp values from 2 to n

dp[i] = max_productStore the best product for integer i

public class IntegerBreak {
    public static int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int maxProduct = 0;
            for (int j = 1; j < i; j++) {
                int left = Math.max(j, dp[j]);
                int right = Math.max(i - j, dp[i - j]);
                maxProduct = Math.max(maxProduct, left * right);
            }
            dp[i] = maxProduct;
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(integerBreak(10)); // Expected output: 36
    }
}

Line Notes

int[] dp = new int[n + 1];Create dp array for storing results

dp[1] = 1;Base case initialization

for (int i = 2; i <= n; i++) {Iterate through all integers up to n

dp[i] = maxProduct;Save the maximum product for i

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

int integerBreak(int n) {
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        int maxProduct = 0;
        for (int j = 1; j < i; j++) {
            int left = max(j, dp[j]);
            int right = max(i - j, dp[i - j]);
            maxProduct = max(maxProduct, left * right);
        }
        dp[i] = maxProduct;
    }
    return dp[n];
}

int main() {
    cout << integerBreak(10) << endl; // Expected output: 36
    return 0;
}

Line Notes

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

dp[1] = 1;Set base case

for (int i = 2; i <= n; i++) {Fill dp array iteratively

dp[i] = maxProduct;Store best product for i

function integerBreak(n) {
    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        let maxProduct = 0;
        for (let j = 1; j < i; j++) {
            let left = Math.max(j, dp[j]);
            let right = Math.max(i - j, dp[i - j]);
            maxProduct = Math.max(maxProduct, left * right);
        }
        dp[i] = maxProduct;
    }
    return dp[n];
}

// Test
console.log(integerBreak(10)); // Expected output: 36

Line Notes

const dp = new Array(n + 1).fill(0);Create dp array initialized to zero

dp[1] = 1;Base case for smallest integer

for (let i = 2; i <= n; i++) {Compute dp values from bottom up

dp[i] = maxProduct;Store maximum product for i

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Two nested loops: outer for i up to n, inner for j up to i, resulting in quadratic time.

💡 For n=1000, about 1 million operations, efficient for interviews.

Interview Verdict: Accepted

Tabulation is often preferred for clarity and iterative control.

🧠

Space Optimized Bottom-Up

💡 Since dp only depends on smaller indices, we can use a single 1D array without extra space, keeping the same time complexity but reducing memory usage.

Intuition

Reuse the dp array in place, updating values as we go, since we only need previously computed results.

Algorithm

1. Initialize a 1D dp array with dp[1] = 1.
2. Iterate i from 2 to n, for each i try all cuts j from 1 to i-1.
3. Update dp[i] with the maximum product using dp[j] and dp[i-j].
4. Return dp[n] as the final answer.

💡 This approach uses the same logic as tabulation but emphasizes efficient memory use.

Recurrence:dp[i] = max_{1 ≤ j < i} (max(j, dp[j]) * max(i-j, dp[i-j]))

</>

Code

def integer_break(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        max_product = 0
        for j in range(1, i):
            max_product = max(max_product, max(j, dp[j]) * max(i - j, dp[i - j]))
        dp[i] = max_product
    return dp[n]

# Driver code
if __name__ == '__main__':
    print(integer_break(10))  # Expected output: 36

Line Notes

dp = [0] * (n + 1)Create dp array to store max products

dp[1] = 1Base case initialization

for i in range(2, n + 1):Iterate over all integers up to n

dp[i] = max_productStore the best product found for i

public class IntegerBreak {
    public static int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int maxProduct = 0;
            for (int j = 1; j < i; j++) {
                maxProduct = Math.max(maxProduct, Math.max(j, dp[j]) * Math.max(i - j, dp[i - j]));
            }
            dp[i] = maxProduct;
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(integerBreak(10)); // Expected output: 36
    }
}

Line Notes

int[] dp = new int[n + 1];Initialize dp array

dp[1] = 1;Set base case

for (int i = 2; i <= n; i++) {Compute dp values iteratively

dp[i] = maxProduct;Store maximum product for i

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

int integerBreak(int n) {
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        int maxProduct = 0;
        for (int j = 1; j < i; j++) {
            maxProduct = max(maxProduct, max(j, dp[j]) * max(i - j, dp[i - j]));
        }
        dp[i] = maxProduct;
    }
    return dp[n];
}

int main() {
    cout << integerBreak(10) << endl; // Expected output: 36
    return 0;
}

Line Notes

vector<int> dp(n + 1, 0);Create dp vector initialized to zero

dp[1] = 1;Base case for smallest integer

for (int i = 2; i <= n; i++) {Fill dp array from bottom up

dp[i] = maxProduct;Store best product for i

function integerBreak(n) {
    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        let maxProduct = 0;
        for (let j = 1; j < i; j++) {
            maxProduct = Math.max(maxProduct, Math.max(j, dp[j]) * Math.max(i - j, dp[i - j]));
        }
        dp[i] = maxProduct;
    }
    return dp[n];
}

// Test
console.log(integerBreak(10)); // Expected output: 36

Line Notes

const dp = new Array(n + 1).fill(0);Initialize dp array

dp[1] = 1;Set base case

for (let i = 2; i <= n; i++) {Iterate through all integers

dp[i] = maxProduct;Store maximum product for i

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Same time complexity as tabulation but uses minimal space.

💡 This is the most memory-efficient DP approach for this problem.

Interview Verdict: Accepted

Space optimization is a good final step to demonstrate mastery.

📊

All Approaches - One-Glance Tradeoffs

💡 Memoization or tabulation are best to code in interviews; brute force is only for explanation; space optimization is optional.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes	No	Mention only - never code
2. Top-Down Memoization	O(n^2)	O(n)	No (due to caching)	Yes	Good to code if comfortable with recursion
3. Bottom-Up Tabulation	O(n^2)	O(n)	No	Yes	Preferred approach to code
4. Space Optimized Bottom-Up	O(n^2)	O(n)	No	Yes	Mention as optimization, code if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when and how to present them in an interview.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force recursive approach to show understanding.Step 3: Introduce memoization to optimize recursion.Step 4: Present bottom-up tabulation for iterative clarity.Step 5: Optionally mention space optimization for completeness.Step 6: Code the tabulation or memoization approach as preferred.Step 7: Test with edge cases and explain complexity.

Time Allocation

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

What the Interviewer Tests

Understanding of recursion and DP, ability to optimize naive solutions, clarity in explaining state and transitions, and coding accuracy.

Common Follow-ups

• What if n is very large? → Use mathematical formula or fast exponentiation.
• Can you reconstruct the actual cuts? → Store choices in DP and backtrack.

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

🔍

Pattern Recognition

When to Use

1) Problem asks to break integer into parts; 2) Maximize product or sum; 3) Overlapping subproblems exist; 4) Unbounded usage of parts allowed.

Signature Phrases

break integer into at least two partsmaximize the productunbounded knapsack pattern

NOT This Pattern When

Problems that require partitioning without repetition or that maximize sums without unbounded usage.

Similar Problems

Coin Change II - similar unbounded knapsack structureRod Cutting - maximize profit by cutting rodsPerfect Squares - sum of squares decomposition

Practice

1. You are given an array of positive integers and a number k. The task is to determine if the array can be partitioned into k subsets such that the sum of elements in each subset is equal. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm that repeatedly picks the largest element and tries to fit it into subsets

B. Dynamic programming with bitmask tabulation that tracks subset sums for all combinations

C. Simple backtracking without memoization that tries all possible assignments

D. Sorting the array and using a two-pointer technique to pair elements

Solution

1. Step 1: Understand problem constraints

   The problem requires partitioning into equal sum subsets, which is a classic NP-complete problem requiring exploration of subsets.

2. Step 2: Identify algorithmic pattern

   Dynamic programming with bitmask tabulation efficiently explores all subsets and tracks partial sums modulo target, guaranteeing optimality.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask DP covers all subsets systematically [OK]

Hint: Bitmask DP tracks all subset sums efficiently [OK]

Common Mistakes:

• Assuming greedy always works for equal sum partition
• Using backtracking without memoization leads to timeouts

2. 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

3. What is the time complexity of the bottom-up DP solution with binary search for the minimum cost tickets problem, given n travel days?

medium

A. O(n^2) because for each day we scan all future days

B. O(n log n) because for each day we perform 3 binary searches over the days array

C. O(n) because we only iterate once over the days array

D. O(n * 3 * n) due to nested loops over days and durations

Solution

1. Step 1: Identify loops and operations

   Outer loop runs n times (for each day). Inner loop runs 3 times (for each ticket duration). Each inner iteration does a binary search (log n) to find next uncovered day.

2. Step 2: Calculate total complexity

   Total time = n * 3 * log n = O(n log n). Linear scan or nested loops over days would be O(n^2), but binary search reduces it.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search reduces inner loop from O(n) to O(log n) [OK]

Hint: Binary search reduces complexity from quadratic to n log n [OK]

Common Mistakes:

• Assuming inner loop is linear scan
• Ignoring binary search effect
• Confusing space with time complexity

4. What is the time complexity of the space-optimized bottom-up dynamic programming solution for counting the number of ways to make change with n coins and amount W?

medium

A. O(n * W) because for each coin we iterate over all amounts up to W

B. O(n + W) because we iterate over coins and amounts separately

C. O(W^n) due to nested loops over coins and amounts

D. O(n * W) plus O(W) auxiliary space for the dp array

Solution

1. Step 1: Identify loops and their ranges

   Outer loop runs n times (coins), inner loop runs up to W (amount), so time is O(n * W).

2. Step 2: Consider space usage

   DP array size is W+1, so auxiliary space is O(W). Total complexity includes both time and space, but time complexity is the main focus here.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time O(n*W) matches DP approach [OK]

Hint: Time is product of coins and amount; space is dp array size [OK]

Common Mistakes:

• Confusing time with space complexity
• Forgetting auxiliary space for dp array
• Mistaking exponential complexity for DP

5. What is the time complexity of the DP with bitmask tabulation approach for partitioning an array of size n into k equal sum subsets, where the algorithm iterates over all subsets and elements?

medium

A. O(k^n) because it tries all assignments of elements to k buckets

B. O(n * 2^n) because it iterates over all subsets and elements

C. O(n * target) where target is the subset sum

D. O(2^n * n^2) due to nested loops over subsets and elements

Solution

1. Step 1: Identify loops in the algorithm

   The outer loop iterates over all subsets (2^n), inner loop over n elements.

2. Step 2: Calculate total complexity

   Combining loops gives O(n * 2^n). The target sum does not affect iteration count directly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP bitmask iterates all subsets and elements [OK]

Hint: Bitmask DP complexity is n times 2^n subsets [OK]

Common Mistakes:

• Confusing brute force backtracking complexity with DP complexity
• Assuming complexity depends on target sum