🔄 Subsets & Permutations

function subsets(nums) {
    const result = [];
    
    function backtrack(index, current) {
        // Base case: processed all elements
        if (index === nums.length) {
            result.push([...current]);
            return;
        }
        
        // Choice 1: Exclude current element
        backtrack(index + 1, current);
        
        // Choice 2: Include current element
        current.push(nums[index]);
        backtrack(index + 1, current);
        current.pop();
    }
    
    backtrack(0, []);
    return result;
}

// For [1,2,3]: 2^3 = 8 subsets
// [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]

function permute(nums) {
    const result = [];
    
    function backtrack(current, remaining) {
        if (remaining.length === 0) {
            result.push([...current]);
            return;
        }
        
        for (let i = 0; i < remaining.length; i++) {
            // Choose
            current.push(remaining[i]);
            
            // Explore
            const newRemaining = [
                ...remaining.slice(0, i),
                ...remaining.slice(i + 1)
            ];
            backtrack(current, newRemaining);
            
            // Unchoose
            current.pop();
        }
    }
    
    backtrack([], nums);
    return result;
}

// For [1,2,3]: 3! = 6 permutations
// [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

function combine(n, k) {
    const result = [];
    
    function backtrack(start, current) {
        if (current.length === k) {
            result.push([...current]);
            return;
        }
        
        for (let i = start; i <= n; i++) {
            current.push(i);
            backtrack(i + 1, current);
            current.pop();
        }
    }
    
    backtrack(1, []);
    return result;
}

// For n=4, k=2: C(4,2) = 6 combinations
// [1,2], [1,3], [1,4], [2,3], [2,4], [3,4]