040-backtracking-problem-4.md

Backtracking Problem 4

LeetCode: https://leetcode.com/problems/combination-sum-ii/ Difficulty: Medium

Problem

Solve this backtracking problem efficiently.

Brute Force Approach

function solve(nums) {
    const result = [];
    
    // Generate all possibilities
    function backtrack(current, remaining) {
        if (remaining.length === 0) {
            result.push([...current]);
            return;
        }
        
        for (let i = 0; i < remaining.length; i++) {
            current.push(remaining[i]);
            const next = remaining.slice(0, i).concat(remaining.slice(i + 1));
            backtrack(current, next);
            current.pop();
        }
    }
    
    backtrack([], nums);
    return result;
}

⏱️ Time: O(n²) or O(n³)
💾 Space: O(n)

Optimal Approach

function solve(nums) {
    const result = [];
    const used = new Array(nums.length).fill(false);
    
    function backtrack(current) {
        if (current.length === nums.length) {
            result.push([...current]);
            return;
        }
        
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            
            current.push(nums[i]);
            used[i] = true;
            backtrack(current);
            used[i] = false;
            current.pop();
        }
    }
    
    backtrack([]);
    return result;
}

⏱️ Time: O(n) or O(n log n)
💾 Space: O(n) or O(1)

Visual Diagram

Decision Tree:
        []
       / | \
      1  2  3
     /|  |  |\
    2 3  1 3 1 2
    |  |  |  | |  |
   [1,2,3] [1,3,2] ...

Backtrack when complete

---

Visit LeetCode for full problem description.