Combination Sum II (No Reuse, Duplicates)

🎯

Combination Sum II (No Reuse, Duplicates)

mediumBACKTRACKINGAmazonGoogle

Imagine you are organizing a gift basket with a fixed budget, and you want to find all unique combinations of items that exactly match your budget without repeating any item.

💡 This problem asks for all unique combinations of numbers that sum to a target, but each number can only be used once. Beginners often struggle with handling duplicates and ensuring no repeated combinations appear in the output.

📋

Problem Statement

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination. The solution set must not contain duplicate combinations.

1 ≤ candidates.length ≤ 1001 ≤ candidates[i] ≤ 501 ≤ target ≤ 500

💡

Example

Input"candidates = [10,1,2,7,6,1,5], target = 8"

Output[[1,1,6],[1,2,5],[1,7],[2,6]]

We find all unique combinations that sum to 8. Note that [1,1,6] appears only once despite two '1's in candidates.

• Empty candidates array → []
• No combination sums to target → []
• All candidates are the same number and sum to target → single combination
• Target smaller than smallest candidate → []

⚠️

Common Mistakes

Not sorting candidates before recursion

Duplicates cannot be detected and skipped, leading to repeated combinations

✅ Sort candidates array before starting backtracking

Skipping duplicates incorrectly (e.g., skipping all duplicates, not just at same recursion level)

Valid combinations may be missed or duplicates still appear

✅ Only skip duplicates when they appear at the same recursion depth (same for-loop level)

Reusing candidates multiple times despite problem stating no reuse

Output includes invalid combinations with repeated elements

✅ Advance index by i+1 in recursion to avoid reuse of same element

Not pruning recursion when candidate > target

Unnecessary recursion calls increase runtime significantly

✅ Break the loop early when candidate exceeds remaining target

Modifying path list in-place without backtracking properly

Results contain incorrect combinations due to shared references

✅ Use path copies or backtrack by removing last element after recursion

🧠

Brute Force (Pure Recursion with Backtracking)

💡 Starting with brute force helps understand the problem structure and recursion tree, even though it is inefficient and duplicates are not handled optimally.

Intuition

Try every possible combination by recursively choosing or skipping each candidate, and check if the sum matches the target. This explores all subsets.

Algorithm

1. Sort the candidates to help identify duplicates later.
2. Recursively explore each candidate starting from current index.
3. Include the candidate and recurse with reduced target and next index.
4. Exclude the candidate and recurse with next index.

💡 The recursion explores all subsets but does not yet handle duplicates properly, so it may generate repeated combinations.

</>

Code

from typing import List

def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    res = []
    def backtrack(start, path, target):
        if target == 0:
            res.append(path[:])
            return
        if target < 0:
            return
        for i in range(start, len(candidates)):
            # No duplicate handling here
            backtrack(i + 1, path + [candidates[i]], target - candidates[i])
    backtrack(0, [], target)
    return res

# Driver code
if __name__ == '__main__':
    print(combinationSum2([10,1,2,7,6,1,5], 8))

Line Notes

candidates.sort()Sorting helps to identify duplicates in later approaches

def backtrack(start, path, target):Defines recursive function exploring subsets from 'start'

if target == 0:Base case: found a valid combination summing to target

for i in range(start, len(candidates))Try each candidate starting from current index

import java.util.*;

public class CombinationSum2 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (target < 0) return;
        for (int i = start; i < candidates.length; i++) {
            // No duplicate handling here
            path.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum2 sol = new CombinationSum2();
        System.out.println(sol.combinationSum2(new int[]{10,1,2,7,6,1,5}, 8));
    }
}

Line Notes

Arrays.sort(candidates);Sorting to prepare for duplicate detection in better approaches

private void backtrack(...)Recursive helper exploring subsets from 'start' index

if (target == 0)Found a valid combination, add a copy to results

for (int i = start; i < candidates.length; i++)Try each candidate from current index

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        vector<int> path;
        backtrack(candidates, target, 0, path, res);
        return res;
    }

    void backtrack(vector<int>& candidates, int target, int start, vector<int>& path, vector<vector<int>>& res) {
        if (target == 0) {
            res.push_back(path);
            return;
        }
        if (target < 0) return;
        for (int i = start; i < candidates.size(); i++) {
            // No duplicate handling here
            path.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, res);
            path.pop_back();
        }
    }
};

int main() {
    Solution sol;
    vector<int> candidates = {10,1,2,7,6,1,5};
    vector<vector<int>> res = sol.combinationSum2(candidates, 8);
    for (auto &comb : res) {
        cout << "[";
        for (int i = 0; i < comb.size(); i++) {
            cout << comb[i];
            if (i != comb.size() - 1) cout << ",";
        }
        cout << "]\n";
    }
    return 0;
}

Line Notes

sort(candidates.begin(), candidates.end());Sort to prepare for duplicate handling later

void backtrack(...)Recursive function exploring subsets from 'start'

if (target == 0)Base case: found valid combination

for (int i = start; i < candidates.size(); i++)Try each candidate starting from current index

function combinationSum2(candidates, target) {
    candidates.sort((a,b) => a - b);
    const res = [];
    function backtrack(start, path, target) {
        if (target === 0) {
            res.push([...path]);
            return;
        }
        if (target < 0) return;
        for (let i = start; i < candidates.length; i++) {
            // No duplicate handling here
            path.push(candidates[i]);
            backtrack(i + 1, path, target - candidates[i]);
            path.pop();
        }
    }
    backtrack(0, [], target);
    return res;
}

// Test
console.log(combinationSum2([10,1,2,7,6,1,5], 8));

Line Notes

candidates.sort((a,b) => a - b);Sort to help identify duplicates in better approaches

function backtrack(start, path, target)Recursive helper exploring subsets from 'start'

if (target === 0)Found a valid combination, add a copy to results

for (let i = start; i < candidates.length; i++)Try each candidate starting from current index

⏱

Complexity

TimeO(2^n * n)

SpaceO(n)

We explore all subsets (2^n) and copying paths costs O(n) each time we find a valid combination.

💡 For n=15, 2^15=32768 subsets, which is already large and inefficient.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow and produces duplicates, but it helps understand the problem structure.

🧠

Backtracking with Sorting and Duplicate Skipping

💡 This approach improves brute force by sorting and skipping duplicates at the same recursion level to avoid repeated combinations.

Intuition

Sort candidates so duplicates are adjacent. When iterating, skip candidates equal to the previous one at the same recursion depth to avoid duplicate combinations.

Algorithm

1. Sort candidates to group duplicates.
2. Recursively explore candidates starting from current index.
3. Skip candidates that are the same as previous at the same recursion level.
4. Include candidate and recurse with next index and reduced target.

💡 Skipping duplicates at the same recursion level is key to avoid repeated combinations.

</>

Code

from typing import List

def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    res = []
    def backtrack(start, path, target):
        if target == 0:
            res.append(path[:])
            return
        if target < 0:
            return
        prev = -1
        for i in range(start, len(candidates)):
            if candidates[i] == prev:
                continue
            prev = candidates[i]
            backtrack(i + 1, path + [candidates[i]], target - candidates[i])
    backtrack(0, [], target)
    return res

# Driver code
if __name__ == '__main__':
    print(combinationSum2([10,1,2,7,6,1,5], 8))

Line Notes

candidates.sort()Sort to group duplicates for skipping

prev = -1Initialize previous candidate to track duplicates at this level

if candidates[i] == prev:Skip duplicate candidates at same recursion depth

backtrack(i + 1, path + [candidates[i]], target - candidates[i])Recurse with next index and updated target

import java.util.*;

public class CombinationSum2 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (target < 0) return;
        int prev = -1;
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] == prev) continue;
            prev = candidates[i];
            path.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum2 sol = new CombinationSum2();
        System.out.println(sol.combinationSum2(new int[]{10,1,2,7,6,1,5}, 8));
    }
}

Line Notes

Arrays.sort(candidates);Sort to group duplicates for skipping

int prev = -1;Track previous candidate to skip duplicates at this level

if (candidates[i] == prev) continue;Skip duplicate candidates at same recursion depth

backtrack(candidates, target - candidates[i], i + 1, path, res);Recurse with next index and updated target

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        vector<int> path;
        backtrack(candidates, target, 0, path, res);
        return res;
    }

    void backtrack(vector<int>& candidates, int target, int start, vector<int>& path, vector<vector<int>>& res) {
        if (target == 0) {
            res.push_back(path);
            return;
        }
        if (target < 0) return;
        int prev = -1;
        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] == prev) continue;
            prev = candidates[i];
            path.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, res);
            path.pop_back();
        }
    }
};

int main() {
    Solution sol;
    vector<int> candidates = {10,1,2,7,6,1,5};
    vector<vector<int>> res = sol.combinationSum2(candidates, 8);
    for (auto &comb : res) {
        cout << "[";
        for (int i = 0; i < comb.size(); i++) {
            cout << comb[i];
            if (i != comb.size() - 1) cout << ",";
        }
        cout << "]\n";
    }
    return 0;
}

Line Notes

sort(candidates.begin(), candidates.end());Sort to group duplicates for skipping

int prev = -1;Track previous candidate to skip duplicates at this level

if (candidates[i] == prev) continue;Skip duplicate candidates at same recursion depth

backtrack(candidates, target - candidates[i], i + 1, path, res);Recurse with next index and updated target

function combinationSum2(candidates, target) {
    candidates.sort((a,b) => a - b);
    const res = [];
    function backtrack(start, path, target) {
        if (target === 0) {
            res.push([...path]);
            return;
        }
        if (target < 0) return;
        let prev = -1;
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] === prev) continue;
            prev = candidates[i];
            path.push(candidates[i]);
            backtrack(i + 1, path, target - candidates[i]);
            path.pop();
        }
    }
    backtrack(0, [], target);
    return res;
}

// Test
console.log(combinationSum2([10,1,2,7,6,1,5], 8));

Line Notes

candidates.sort((a,b) => a - b);Sort to group duplicates for skipping

let prev = -1;Track previous candidate to skip duplicates at this level

if (candidates[i] === prev) continue;Skip duplicate candidates at same recursion depth

backtrack(i + 1, path, target - candidates[i]);Recurse with next index and updated target

⏱

Complexity

TimeO(2^n * n)

SpaceO(n)

Still explores subsets but pruning duplicates reduces redundant paths; copying paths costs O(n).

💡 For n=15, this is much faster than brute force but still exponential in worst case.

Interview Verdict: Accepted / Efficient for typical inputs

This is the standard approach to solve the problem efficiently in interviews.

🧠

Backtracking with Sorting, Duplicate Skipping, and Early Pruning

💡 This approach adds early pruning by stopping recursion when candidates exceed the remaining target, improving efficiency.

Intuition

Since candidates are sorted, if the current candidate is greater than the remaining target, no need to explore further as all next candidates will be larger.

Algorithm

1. Sort candidates to group duplicates and enable pruning.
2. Recursively explore candidates starting from current index.
3. Skip duplicates at the same recursion level.
4. If candidate > target, break early to prune search space.
5. Include candidate and recurse with next index and reduced target.

💡 Early pruning reduces unnecessary recursion calls, speeding up the search.

</>

Code

from typing import List

def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    res = []
    def backtrack(start, path, target):
        if target == 0:
            res.append(path[:])
            return
        prev = -1
        for i in range(start, len(candidates)):
            if candidates[i] > target:
                break
            if candidates[i] == prev:
                continue
            prev = candidates[i]
            backtrack(i + 1, path + [candidates[i]], target - candidates[i])
    backtrack(0, [], target)
    return res

# Driver code
if __name__ == '__main__':
    print(combinationSum2([10,1,2,7,6,1,5], 8))

Line Notes

candidates.sort()Sort to enable duplicate skipping and pruning

if candidates[i] > target:Prune recursion early if candidate exceeds remaining target

if candidates[i] == prev:Skip duplicates at same recursion level

backtrack(i + 1, path + [candidates[i]], target - candidates[i])Recurse with next index and updated target

import java.util.*;

public class CombinationSum2 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        int prev = -1;
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > target) break;
            if (candidates[i] == prev) continue;
            prev = candidates[i];
            path.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum2 sol = new CombinationSum2();
        System.out.println(sol.combinationSum2(new int[]{10,1,2,7,6,1,5}, 8));
    }
}

Line Notes

Arrays.sort(candidates);Sort to enable duplicate skipping and pruning

if (candidates[i] > target) break;Prune recursion early if candidate exceeds remaining target

if (candidates[i] == prev) continue;Skip duplicates at same recursion level

backtrack(candidates, target - candidates[i], i + 1, path, res);Recurse with next index and updated target

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        vector<int> path;
        backtrack(candidates, target, 0, path, res);
        return res;
    }

    void backtrack(vector<int>& candidates, int target, int start, vector<int>& path, vector<vector<int>>& res) {
        if (target == 0) {
            res.push_back(path);
            return;
        }
        int prev = -1;
        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] > target) break;
            if (candidates[i] == prev) continue;
            prev = candidates[i];
            path.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, res);
            path.pop_back();
        }
    }
};

int main() {
    Solution sol;
    vector<int> candidates = {10,1,2,7,6,1,5};
    vector<vector<int>> res = sol.combinationSum2(candidates, 8);
    for (auto &comb : res) {
        cout << "[";
        for (int i = 0; i < comb.size(); i++) {
            cout << comb[i];
            if (i != comb.size() - 1) cout << ",";
        }
        cout << "]\n";
    }
    return 0;
}

Line Notes

sort(candidates.begin(), candidates.end());Sort to enable duplicate skipping and pruning

if (candidates[i] > target) break;Prune recursion early if candidate exceeds remaining target

if (candidates[i] == prev) continue;Skip duplicates at same recursion level

backtrack(candidates, target - candidates[i], i + 1, path, res);Recurse with next index and updated target

function combinationSum2(candidates, target) {
    candidates.sort((a,b) => a - b);
    const res = [];
    function backtrack(start, path, target) {
        if (target === 0) {
            res.push([...path]);
            return;
        }
        let prev = -1;
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > target) break;
            if (candidates[i] === prev) continue;
            prev = candidates[i];
            path.push(candidates[i]);
            backtrack(i + 1, path, target - candidates[i]);
            path.pop();
        }
    }
    backtrack(0, [], target);
    return res;
}

// Test
console.log(combinationSum2([10,1,2,7,6,1,5], 8));

Line Notes

candidates.sort((a,b) => a - b);Sort to enable duplicate skipping and pruning

if (candidates[i] > target) break;Prune recursion early if candidate exceeds remaining target

if (candidates[i] === prev) continue;Skip duplicates at same recursion level

backtrack(i + 1, path, target - candidates[i]);Recurse with next index and updated target

⏱

Complexity

TimeO(2^n * n)

SpaceO(n)

Early pruning reduces recursion calls, but worst case remains exponential; path copying costs O(n).

💡 For n=20, pruning can significantly reduce runtime compared to brute force.

Interview Verdict: Accepted / Optimal backtracking solution

This is the recommended approach to implement in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 3 is the best to code in interviews; Approach 1 is only for explanation; Approach 2 is a stepping stone.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n * n)	O(n)	Yes (deep recursion)	Yes	Mention only - never code
2. Backtracking with Duplicate Skipping	O(2^n * n)	O(n)	Yes	Yes	Good to explain and code if time permits
3. Backtracking with Duplicate Skipping and Early Pruning	O(2^n * n) but faster in practice	O(n)	Yes	Yes	Best approach to implement 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 problem constraints and ask about duplicates and reuse.Step 2: Present brute force recursion to explore all subsets.Step 3: Improve by sorting and skipping duplicates at recursion level.Step 4: Add early pruning to optimize runtime.Step 5: Code the final approach and test with examples.

Time Allocation

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

What the Interviewer Tests

Ability to handle duplicates correctly, implement backtracking with pruning, and communicate complexity tradeoffs.

Common Follow-ups

• What if candidates can be reused unlimited times? → Use Combination Sum I approach.
• How to handle very large input arrays? → Use pruning and possibly iterative methods.
• Can you return count of combinations instead of all? → Use DP or memoization.
• What if output order matters? → Sort results or use ordered data structures.

💡 These follow-ups test your flexibility and understanding of variations on the problem.

🔍

Pattern Recognition

When to Use

1) Need all unique combinations; 2) Each element used once; 3) Sum constraint; 4) Input may have duplicates.

Signature Phrases

unique combinationseach number only onceno duplicate combinationssum to target

NOT This Pattern When

Problems allowing unlimited reuse or permutations without sum constraints

Similar Problems

Combination Sum I - allows reuse of elementsSubsets II - find unique subsets without sum constraintPermutations II - unique permutations with duplicates

Practice

1. You need to generate all unique groups of size k from numbers 1 to n without repetition, where order within each group does not matter. Which algorithmic approach guarantees generating all such groups efficiently without duplicates?

easy

A. Backtracking that explores all number choices with pruning to avoid duplicates

B. Greedy selection picking the smallest available number until group size is reached

C. Dynamic programming to count subsets but not generate them explicitly

D. Sorting all numbers and then selecting consecutive sequences of length k

Solution

1. Step 1: Understand the problem requires all unique combinations of size k from n numbers

   Greedy or sorting consecutive sequences do not guarantee all unique combinations without duplicates.

2. Step 2: Backtracking with pruning systematically explores all valid combinations and avoids duplicates by controlling start indices

   This approach ensures all unique groups are generated efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking with pruning is the standard approach for combinations [OK]

Hint: Backtracking with pruning avoids duplicates efficiently [OK]

Common Mistakes:

• Thinking greedy or sorting consecutive sequences generate all combinations

2. You are given an array of positive integers and a target sum K. You need to find how many subsets of the array sum exactly to K. Which of the following approaches guarantees an optimal solution with polynomial time complexity?

easy

A. Greedy algorithm that picks the largest elements first until the sum reaches or exceeds K

B. Pure recursion that tries all subsets without memoization

C. Dynamic Programming using a bottom-up tabulation approach that counts subsets for all sums up to K

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

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all subsets summing to K, which involves exploring combinations, not just pairs or greedy picks.

2. Step 2: Evaluate approaches

   Greedy and two-pointer methods fail because they do not consider all subsets. Pure recursion is correct but exponential. Bottom-up DP efficiently counts subsets for all sums up to K, ensuring polynomial time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP tabulation counts subsets for all sums -> polynomial time [OK]

Hint: Counting subsets with sum K requires DP, not greedy or two-pointer [OK]

Common Mistakes:

• Assuming greedy or two-pointer works for subset sums
• Confusing counting subsets with finding pairs

3. Consider the following Python function implementing backtracking with bitmask memoization for partitioning an array into k equal sum subsets. Given nums = [4, 3, 2, 3, 5, 2, 1] and k = 4, what is the final return value of canPartitionKSubsets(nums, k)?

easy

A. True

B. False

C. Raises an exception due to index error

D. Returns None

Solution

1. Step 1: Calculate total and target sum

   Total sum is 4+3+2+3+5+2+1=20, target per subset = 20/4=5.

2. Step 2: Trace backtracking with sorted nums

   Sorted nums: [5,4,3,3,2,2,1]. The algorithm finds subsets: {5}, {4,1}, {3,2}, {3,2} all summing to 5, so returns True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All subsets sum to target, so partition possible [OK]

Hint: Sum divisible by k and backtracking finds valid subsets [OK]

Common Mistakes:

• Miscounting sum or target
• Assuming no solution due to order

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

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

medium

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

B. dp[0] = 1

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

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

Solution

1. Step 1: Analyze iteration order

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

2. Step 2: Correct iteration direction

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

3. Final Answer:

   Option A -> Option A

4. Quick Check:

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

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

Common Mistakes:

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

5. What is the time complexity of generating all subsets of an array of size n using the bit manipulation approach shown below?

medium

A. O(2^n * n) because for each of the 2^n masks, we check n bits to build the subset

B. O(2^n) because there are 2^n subsets and each subset is generated in constant time

C. O(n^2) because of nested loops over n elements

D. O(n * 2^n) because each of the 2^n subsets requires iterating over n elements

Solution

1. Step 1: Identify outer loop complexity

   The outer loop runs 2^n times, once per subset mask.

2. Step 2: Identify inner loop complexity

   For each mask, the inner loop iterates n times to check each bit.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Total time is 2^n * n due to mask and bit checks [OK]

Hint: Each subset requires checking n bits -> O(n*2^n) [OK]

Common Mistakes:

• Assuming subset generation is O(2^n) ignoring bit checks
• Confusing n^2 with 2^n * n