Bird
Raised Fist0

Identify the bug: ```python def combinationSum2(candidates, target): candidates.sort() res = [] def backtrack(start, path, target): if target == 0: res.append(path[:]) return for i in range(start, len(candidates)): if i > start and candidates[i] == candidates[i-1]: continue if candidates[i] > target: break backtrack(i+1, path + [candidates[i]], target - candidates[i]) backtrack(0, [], target) return res ``` What is the cause of duplicates in the output?

medium🐞 Bug Q7 of Q15
Subsets & Combinations - Combination Sum II (No Reuse, Duplicates)
The following Python code attempts to solve Combination Sum II but sometimes returns duplicate combinations. Identify the bug: ```python def combinationSum2(candidates, target): candidates.sort() res = [] def backtrack(start, path, target): if target == 0: res.append(path[:]) return for i in range(start, len(candidates)): if i > start and candidates[i] == candidates[i-1]: continue if candidates[i] > target: break backtrack(i+1, path + [candidates[i]], target - candidates[i]) backtrack(0, [], target) return res ``` What is the cause of duplicates in the output?
AThe code does not sort the candidates before backtracking.
BThe duplicate skipping condition is incorrect; it should be 'if i > start and candidates[i] == candidates[i-1]'.
CThe recursive call uses 'i' instead of 'i+1' causing reuse of elements.
DThe base case does not return after appending a valid combination.
Step-by-Step Solution
Solution:
  1. Step 1: Analyze duplicate skipping

    The condition 'if i > start and candidates[i] == candidates[i-1]' is correctly implemented to skip duplicates.
  2. Step 2: Check sorting

    Candidates are sorted at the start, so sorting is not the issue.
  3. Step 3: Check recursive call

    Recursive call uses 'i+1' correctly to avoid reuse.
  4. Step 4: Check base case

    Base case appends path and returns immediately, preventing duplicates.
  5. Final Answer:

    The duplicate skipping condition is incorrect; it should be 'if i > start and candidates[i] == candidates[i-1]'. -> Option B
  6. Quick Check:

    Fixing duplicate skipping condition removes duplicates [OK]
Quick Trick: Correct duplicate skipping condition is critical [OK]
Common Mistakes:
MISTAKES
  • Misunderstanding duplicate skipping condition
  • Forgetting to sort candidates
  • Using wrong indices in recursion
Trap Explanation:
PITFALL
  • Option D is incorrect because the base case returns properly; the bug is in duplicate skipping condition.
Interviewer Note:
CONTEXT
  • Tests debugging skills and understanding of backtracking control flow.
Master "Combination Sum II (No Reuse, Duplicates)" in Subsets & Combinations

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Subsets & Combinations Quizzes