basic-backtracking-test.js

/**
 * Problem: Subsets (Power Set)
 *
 * Given an array of distinct integers `nums`, return all possible subsets (the power set).
 * Each subset must be in non-descending order (order of input), and the full result must not contain duplicates.
 *
 * You must return all subsets, including:
 * - The empty subset []
 * - Single element subsets [x]
 * - All combinations up to the full array [x, y, z, ...]
 *
 * Example:
 * Input: [1, 2, 3]
 * Output:
 * [
 *   [], [1], [2], [3],
 *   [1, 2], [1, 3], [2, 3],
 *   [1, 2, 3]
 * ]
 *
 * Use backtracking to explore all inclusion/exclusion decisions per element.
 */
function subsets(nums) {
    const result = [];
    backtrack(0, []);
    return result;
}

function backtrack(startIndex, path) {
    
    // 1. Add current subset to result
    // 2. Loop over choices starting from startIndex
    // 3. Choose an element
    // 4. Recurse with next index
    // 5. Backtrack (remove last element)
}
function testSubsets() {
    const tests = [
        {
            input: [1],
            expected: [
                [], [1]
            ]
        },
        {
            input: [1, 2],
            expected: [
                [], [1], [2], [1, 2]
            ]
        },
        {
            input: [1, 2, 3],
            expected: [
                [], [1], [2], [3],
                [1, 2], [1, 3], [2, 3],
                [1, 2, 3]
            ]
        }
    ];

    for (let { input, expected } of tests) {
        const output = subsets(input);
        const sort = arr => arr.map(a => a.slice().sort()).sort();
        const match = JSON.stringify(sort(output)) === JSON.stringify(sort(expected));
        console.log(`Input: ${JSON.stringify(input)} → ${match ? '✅ PASS' : '❌ FAIL'}`);
    }
}
testSubsets()