Combination Sum II (No Reuse, Duplicates)

📋

Combination Sum II (No Reuse, Duplicates)

Edge cases:

</>

IDE

def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:public List<List<Integer>> combinationSum2(int[] candidates, int target)vector<vector<int>> combinationSum2(vector<int>& candidates, int target)function combinationSum2(candidates, target)

def combinationSum2(candidates, target):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    // Write your solution here
    return {};
}

function combinationSum2(candidates, target) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[1,1,6],[1,2,5],[1,7],[2,6],[1,1,6]]Duplicates not skipped at the same recursion depth, causing repeated combinations.✅ Add condition to skip candidates[i] if candidates[i] == candidates[i-1] and i > start.

Wrong: [[1,2,2],[5],[2,2,1]]Order of elements not normalized or duplicates not skipped, causing repeated combinations with different order.✅ Sort candidates and skip duplicates at the same recursion level; ensure output combinations are sorted.

Wrong: [[1,1],[1,1],[1,1],[1,1]]Duplicate combinations generated due to missing duplicate skipping in input with all identical elements.✅ Skip duplicates at the same recursion depth by checking candidates[i] == candidates[i-1].

Wrong: [[2,2,3],[7]]Treating problem as unbounded knapsack, allowing reuse of candidates.✅ Increment start index in recursion to prevent reuse: backtrack(i+1, ...).

Wrong: Timeout or no outputBrute force exponential complexity without pruning or duplicate skipping.✅ Implement pruning by stopping recursion when candidate > remaining target and skip duplicates.

✓

Test Cases

Focus on handling empty and minimal inputs correctly before moving on.

Ensure your recursion correctly handles no reuse and duplicates before tackling tricky cases.

Optimize your solution with pruning and duplicate skipping to handle large inputs.

t1_01basic

Input{"candidates":[10,1,2,7,6,1,5],"target":8}

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

⏱ Performance - must finish in 2000ms

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

💡 Try sorting candidates and use backtracking to explore combinations.

💡 Skip duplicates at the same recursion depth to avoid repeated combinations.

💡 Use a condition to skip candidates[i] if it's the same as candidates[i-1] at the same level.

Why it failed: Failed to handle duplicates properly; likely missing duplicate skipping logic at the same recursion level. Fix by adding a check to skip candidates[i] if candidates[i] == candidates[i-1] and i > start.

✓ Correctly handles duplicates and finds all unique combinations.

t1_02basic

Input{"candidates":[2,5,2,1,2],"target":5}

Expected[[1,2,2],[5]]

⏱ Performance - must finish in 2000ms

Unique combinations summing to 5 are [1,2,2] and [5]. Duplicate 2's handled correctly.

💡 Sort candidates to group duplicates together.

💡 Use backtracking with duplicate skipping to avoid repeated combinations.

💡 Skip candidates[i] if it's the same as candidates[i-1] at the same recursion depth.

Why it failed: Incorrect output due to missing duplicate skipping; duplicates cause repeated combinations. Fix by skipping candidates[i] when equal to candidates[i-1] at the same recursion level.

✓ Correctly returns unique combinations without duplicates.

t2_01edge

Input{"candidates":[],"target":7}

Expected[]

⏱ Performance - must finish in 2000ms

Empty candidates array means no combinations possible.

💡 Check if candidates array is empty before processing.

💡 Backtracking should return empty list if no candidates.

💡 Return empty list immediately if candidates is empty.

Why it failed: Code crashes or returns non-empty result on empty candidates. Fix by adding a base case to return [] if candidates is empty.

✓ Correctly handles empty candidates input.

t2_02edge

Input{"candidates":[3],"target":3}

Expected[[3]]

⏱ Performance - must finish in 2000ms

Single element equal to target forms one valid combination.

💡 Test base case with single candidate equal to target.

💡 Backtracking should include candidate if it equals target.

💡 Return [[candidate]] if candidate equals target.

Why it failed: Fails to include single candidate equal to target. Fix by checking if candidate equals target and adding it to results.

✓ Correctly returns single-element combination matching target.

t2_03edge

Input{"candidates":[1,1,1,1],"target":2}

Expected[[1,1]]

⏱ Performance - must finish in 2000ms

All candidates identical; only one unique combination of two 1's sums to 2.

💡 Handle duplicates carefully to avoid repeated combinations.

💡 Skip duplicates at the same recursion depth.

💡 Use condition to skip candidates[i] if candidates[i] == candidates[i-1] at same level.

Why it failed: Returns multiple duplicate combinations due to missing duplicate skipping. Fix by skipping duplicates at the same recursion level.

✓ Correctly returns single unique combination despite duplicates.

t2_04edge

Input{"candidates":[5,10,12],"target":3}

Expected[]

⏱ Performance - must finish in 2000ms

Target smaller than smallest candidate means no valid combinations.

💡 Check if target is smaller than smallest candidate.

💡 Backtracking should return empty list if no candidates fit target.

💡 Return [] immediately if target < min(candidates).

Why it failed: Incorrectly returns non-empty result when target < smallest candidate. Fix by pruning recursion when candidate > target.

✓ Correctly returns empty list when no candidates fit target.

t3_01corner

Input{"candidates":[1,2,3,4,5],"target":10}

Expected[[1,2,3,4],[1,4,5],[2,3,5]]

⏱ Performance - must finish in 2000ms

Multiple unique combinations sum to 10 without reuse: [1,2,3,4], [1,4,5], and [2,3,5].

💡 Check that each candidate is used at most once.

💡 Avoid reusing candidates by incrementing start index in recursion.

💡 Use start = i + 1 in recursive calls to prevent reuse.

Why it failed: Incorrect output includes repeated use of candidates or misses valid combinations. Fix by ensuring recursive calls use start = i + 1 to avoid reuse and explore all combinations.

✓ Correctly enforces no reuse of candidates and finds all unique combinations.

t3_02corner

Input{"candidates":[2,3,6,7],"target":7}

Expected[[7]]

⏱ Performance - must finish in 2000ms

Only single candidate 7 sums to target; no reuse allowed.

💡 Do not treat problem as unbounded knapsack (no reuse).

💡 Ensure each candidate is used once by incrementing start index.

💡 Avoid adding same candidate multiple times by using start = i + 1.

Why it failed: Incorrectly includes [2,2,3] or other repeated candidates. Fix by incrementing start index to prevent reuse.

✓ Correctly distinguishes 0/1 usage from unbounded.

t3_03corner

Input{"candidates":[1,1,2,5],"target":4}

Expected[[1,1,2]]

⏱ Performance - must finish in 2000ms

Duplicate 1's handled correctly; only one unique combination sums to 4.

💡 Beware of greedy approaches that pick first candidates only.

💡 Backtracking explores all subsets with duplicate skipping.

💡 Use sorting and skip duplicates at same recursion level to avoid missing combos.

Why it failed: Greedy approach misses [1,1,2] and returns incomplete results. Fix by full backtracking with duplicate skipping.

✓ Backtracking correctly finds all unique combinations.

t4_01performance

Input{"candidates":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50],"target":250}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 candidates and target=250; O(2^n * n) brute force will time out.

💡 Brute force exponential time will not finish in time.

💡 Use backtracking with pruning and duplicate skipping to optimize.

💡 Sort candidates and prune recursion when candidate > remaining target.

Why it failed: TLE due to exponential brute force complexity O(2^n * n). Fix by pruning and skipping duplicates.

✓ Algorithm runs within time limit using pruning and duplicate skipping.

Practice

1. You are given a string containing letters and digits. You need to generate all possible strings by toggling the case of each letter independently, while digits remain unchanged. Which algorithmic approach guarantees generating all valid permutations efficiently?

easy

A. Backtracking with include/exclude choices for each letter's case

B. Sorting the string and then generating permutations by swapping adjacent characters

C. Dynamic programming using a bottom-up table to store partial permutations

D. Greedy algorithm that toggles letters only when it reduces the lexicographical order

Solution

1. Step 1: Understand problem constraints

   The problem requires exploring all combinations of letter cases, which is a classic subsets problem where each letter can be included as lowercase or uppercase.

2. Step 2: Identify suitable algorithm

   Backtracking with include/exclude choices for each letter's case systematically explores all 2^k combinations, ensuring completeness and correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores all subsets of letter cases [OK]

Hint: Toggle letter cases via backtracking subsets [OK]

Common Mistakes:

• Thinking greedy can find all permutations
• Using DP that doesn't fit subsets pattern

2. Consider the following Python code implementing letter case permutation using backtracking with in-place modification. What is the final output when the input string is "a1b"?

from typing import List

def letterCasePermutation(s: str) -> List[str]:
    res = []
    arr = list(s)
    def backtrack(i: int):
        if i == len(arr):
            res.append(''.join(arr))
            return
        if arr[i].isdigit():
            backtrack(i + 1)
        else:
            arr[i] = arr[i].lower()
            backtrack(i + 1)
            arr[i] = arr[i].upper()
            backtrack(i + 1)
            arr[i] = s[i]  # revert to original
    backtrack(0)
    return res

print(letterCasePermutation("a1b"))

easy

A. ['a1b', 'a1B', 'A1B', 'A1b']

B. ['a1b', 'A1b', 'a1B', 'A1B']

C. ['a1b', 'a1B', 'A1b', 'A1B']

D. ['A1b', 'a1b', 'A1B', 'a1B']

Solution

1. Step 1: Trace backtrack calls for input "a1b"

   Index 0 is 'a' (letter), toggled to 'a' then 'A'. Index 1 is '1' (digit), skipped. Index 2 is 'b' (letter), toggled to 'b' then 'B'.

2. Step 2: Collect permutations in order

   Order of appending: 'a1b', 'a1B', 'A1b', 'A1B'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected toggling order [OK]

Hint: Digits skip toggling; letters toggle lower then upper [OK]

Common Mistakes:

• Swapping order of uppercase/lowercase calls
• Misplacing digit handling

3. Examine the following buggy backtracking code for generating combinations of size k from 1 to n. Which line contains the subtle bug that causes incorrect or duplicate results?

medium

A. Line where for loop iterates from start to n + 1

B. Line where recursion starts from 1 instead of 0

C. Line where path.pop() is called after recursion

D. Line where path is appended directly to result without copying

Solution

1. Step 1: Identify how results are stored

   Appending path directly stores a reference, so all entries in result point to the same list object.

2. Step 2: Understand consequence

   All combinations in result become identical after backtracking modifies path, causing duplicates or incorrect results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Appending a copy (path[:]) fixes the bug [OK]

Hint: Always append a copy of path, not the path itself [OK]

Common Mistakes:

• Forgetting to copy path before appending to result

4. The following code attempts to find the largest divisible subset but contains a subtle bug. Identify the line with the bug.

def largestDivisibleSubset(nums):
    if not nums:
        return []
    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[j] % nums[i] == 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]

medium

A. Line with 'result.append(nums[max_index])'

B. Line with 'dp = [1] * n'

C. Line with 'max_index = 0'

D. Line with 'if nums[j] % nums[i] == 0:'

Solution

1. Step 1: Check divisibility condition

   The condition should be nums[i] % nums[j] == 0 because we want to check if current number is divisible by a smaller number.

2. Step 2: Understand impact of bug

   Using nums[j] % nums[i] == 0 reverses the divisibility logic, causing incorrect dp updates and wrong subsets.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct divisibility check is crucial for correctness [OK]

Hint: Divisibility check direction matters [OK]

Common Mistakes:

• Swapping divisor and dividend in modulo check
• Not sorting input before DP
• Incorrect subset reconstruction

5. What is the time complexity of the optimal iterative approach for generating all unique subsets from an array of length n that may contain duplicates?

medium

A. O(n^2) because of nested loops over the array

B. O(2^n) since each element doubles the subsets

C. O(2^n * n) due to generating all subsets and copying them

D. O(n * 2^n) because sorting dominates the complexity

Solution

1. Step 1: Identify main operations affecting complexity

   Sorting takes O(n log n), which is dominated by subset generation. The algorithm generates all subsets (2^n) and copies subsets of average length O(n).

2. Step 2: Calculate total time complexity

   Generating all subsets is O(2^n), and copying each subset of length up to n leads to O(2^n * n) total time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Copying subsets causes the extra factor n, not just 2^n [OK]

Hint: Copying subsets adds factor n to 2^n subsets [OK]

Common Mistakes:

• Ignoring subset copying cost and saying O(2^n)
• Confusing sorting cost as dominant
• Mistaking nested loops as O(n^2)