Bird
Raised Fist0

The following code attempts to solve Combination Sum (Reuse Allowed). Identify the line containing the subtle bug that causes incorrect results or inefficiency:

medium🐞 Bug Identification Q14 of Q15
Subsets & Combinations - Combination Sum (Reuse Allowed)
The following code attempts to solve Combination Sum (Reuse Allowed). Identify the line containing the subtle bug that causes incorrect results or inefficiency:
def combinationSum(candidates, target):
    candidates.sort()
    result = []
    def backtrack(index, path, target):
        if target == 0:
            result.append(path[:])
            return
        if index == len(candidates) or target < 0:
            return
        max_use = target // candidates[index]
        for count in range(max_use + 1):
            path += [candidates[index]] * count
            backtrack(index + 1, path, target - candidates[index] * count)
            # Missing path restoration here
    backtrack(0, [], target)
    return result
ALine with 'path += [candidates[index]] * count' because path is modified without backtracking (pop).
BLine with 'candidates.sort()' because sorting is unnecessary.
CLine with 'if target == 0:' because it should check for target <= 0.
DLine with 'max_use = target // candidates[index]' because integer division may cause errors.
Step-by-Step Solution
  1. Step 1: Analyze path modification in loop

    Path is extended by count copies of candidates[index] but never restored after recursive call, causing path to grow incorrectly across iterations.
  2. Step 2: Identify missing backtracking step

    Proper backtracking requires removing added elements after recursion to restore path state for next iteration.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Modifying path without restoration leads to incorrect combinations [OK]
Quick Trick: Always restore path after recursion in backtracking [OK]
Common Mistakes:
MISTAKES
  • Forgetting to pop elements after recursion
  • Assuming path copy avoids mutation issues
Trap Explanation:
PITFALL
  • Modifying path in-place without restoration looks simpler but breaks correctness subtly.
Interviewer Note:
CONTEXT
  • Tests attention to detail in backtracking implementation and mutation handling.
Master "Combination Sum (Reuse Allowed)" 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