Subsets and Combinations

function subsetsBitmask(nums) {
    const n = nums.length;
    const result = [];
    const totalSubsets = 1 << n; // 2^n
    
    // Generate all numbers from 0 to 2^n - 1
    for (let mask = 0; mask < totalSubsets; mask++) {
        const subset = [];
        
        // Check each bit in the mask
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subset.push(nums[i]);
            }
        }
        
        result.push(subset);
    }
    
    return result;
}

// Example: [1,2,3] (n=3, so 2^3 = 8 subsets)
// mask=0 (000): []
// mask=1 (001): [1]
// mask=2 (010): [2]
// mask=3 (011): [1,2]
// mask=4 (100): [3]
// mask=5 (101): [1,3]
// mask=6 (110): [2,3]
// mask=7 (111): [1,2,3]

// Each bit represents whether element at that index is included

function subsetsWithDup(nums) {
    const result = [];
    const current = [];
    
    // CRITICAL: Sort to group duplicates together
    nums.sort((a, b) => a - b);
    
    function backtrack(start) {
        result.push([...current]);
        
        for (let i = start; i < nums.length; i++) {
            // Skip duplicates at the same recursion level
            // i > start ensures we take first occurrence
            if (i > start && nums[i] === nums[i - 1]) {
                continue;
            }
            
            current.push(nums[i]);
            backtrack(i + 1);
            current.pop();
        }
    }
    
    backtrack(0);
    return result;
}

// Example: [1,2,2]
// After sort: [1,2,2]
// Result: [[],[1],[1,2],[1,2,2],[2],[2,2]]

// Without skip: would generate [1,2] twice
// With skip: second 2 at same level is skipped

// Why i > start?
// At start, we want to include first duplicate
// At start+1, we skip subsequent duplicates

function combine(n, k) {
    const result = [];
    const current = [];
    
    function backtrack(start) {
        // Base case: found k elements
        if (current.length === k) {
            result.push([...current]);
            return;
        }
        
        // Pruning: need k - current.length more elements
        // Remaining elements: n - start + 1
        // If remaining < needed, no point continuing
        const needed = k - current.length;
        const remaining = n - start + 1;
        
        for (let i = start; i <= n; i++) {
            // Pruning optimization
            if (remaining < needed) break;
            
            current.push(i);
            backtrack(i + 1);
            current.pop();
            
            remaining--; // One less element available
        }
    }
    
    backtrack(1);
    return result;
}

// Example: n=4, k=2
// Result: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

// Without pruning: explores [4] even though needs 2 elements
// With pruning: stops early when not enough elements left

function combinePascal(n, k) {
    const result = [];
    
    function backtrack(start, current) {
        if (current.length === k) {
            result.push([...current]);
            return;
        }
        
        if (start > n) return;
        
        // Two choices: include start or skip start
        // Include start
        current.push(start);
        backtrack(start + 1, current);
        current.pop();
        
        // Skip start
        backtrack(start + 1, current);
    }
    
    backtrack(1, []);
    return result;
}

// This explicitly shows the C(n,k) = C(n-1,k-1) + C(n-1,k) relation
// Include element: reduce to C(n-1, k-1)
// Exclude element: reduce to C(n-1, k)

function combinationSum4(nums, target) {
    const dp = new Array(target + 1).fill(0);
    dp[0] = 1; // One way to make 0: use nothing
    
    // For each sum from 1 to target
    for (let sum = 1; sum <= target; sum++) {
        // Try each number as last number
        for (const num of nums) {
            if (sum - num >= 0) {
                dp[sum] += dp[sum - num];
            }
        }
    }
    
    return dp[target];
}

// Example: [1,2,3], target=4
// Result: 7 (count of combinations)
// [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2], [1,3], [3,1]

// This is NOT backtracking - it's DP because order matters
// dp[i] = sum of dp[i-num] for all num in nums where i-num >= 0

function letterCombinationsBFS(digits) {
    if (!digits) return [];
    
    const phone = {
        '2': 'abc', '3': 'def', '4': 'ghi',
        '5': 'jkl', '6': 'mno', '7': 'pqrs',
        '8': 'tuv', '9': 'wxyz'
    };
    
    const queue = [''];
    
    for (const digit of digits) {
        const letters = phone[digit];
        const size = queue.length;
        
        // Process all combinations at current level
        for (let i = 0; i < size; i++) {
            const combo = queue.shift();
            
            // Add all possible extensions
            for (const letter of letters) {
                queue.push(combo + letter);
            }
        }
    }
    
    return queue;
}

// BFS level-by-level construction
// Each level corresponds to processing one digit
// Queue contains all partial combinations at current level