[Solved] In the following backtracking code for Combination Sum III, which mistake causes incorrect results?def backtrack(start, k, n, path, res): if k == 0 and n == 0: res.... | Subsets & Combinations

Subsets & Combinations - Combination Sum III (K Numbers to N)

In the following backtracking code for Combination Sum III, which mistake causes incorrect results?

def backtrack(start, k, n, path, res):
    if k == 0 and n == 0:
        res.append(path)
        return
    for i in range(start, 10):
        if i > n:
            break
        backtrack(i + 1, k - 1, n - i, path + [i], res)

ANot pruning when i == n

BLoop should start from 1 instead of start

CMissing base case for k < 0

DAppending path directly without copying causes shared reference issues

Step-by-Step Solution

Solution:

Step 1: Analyze append operation
Appending path directly adds a new list each time due to path + [i], so no shared reference issue.
Step 2: Check pruning condition
The code breaks the loop if i > n, but does not prune when i == n, which can cause unnecessary recursion.
Step 3: Correct pruning
Adding pruning for i == n can optimize and prevent incorrect or extra results.
Final Answer:
Not pruning when i == n -> Option A
Quick Check:
Proper pruning avoids unnecessary recursion and incorrect results [OK]

Quick Trick: Prune when i >= n to avoid unnecessary recursion [OK]

Common Mistakes:

MISTAKES

Assuming path append causes shared references
Ignoring pruning conditions
Incorrect loop start

Trap Explanation:

PITFALL

Lack of pruning on i == n can cause extra recursion and incorrect results.

Interviewer Note:

CONTEXT

Tests understanding of pruning and recursion correctness.

Master "Combination Sum III (K Numbers to N)" in Subsets & Combinations

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Subsets & Combinations Quizzes

In the following backtracking code for Combination Sum III, which mistake causes incorrect results?

Step 1: Analyze append operation

Step 2: Check pruning condition

Step 3: Correct pruning

Final Answer:

Quick Check:

Want More Practice?