Tasks

Subsets

Index	Task Name	Task Number	Difficulty	Link
1	Subsets	78	Medium	Link
2	Subsets II	90	Medium	Link
3	Generalized Abbreviation	320	Medium	Link
4	Letter Case Permutation	784	Medium	Link
5	Gray Code	89	Medium	Link
6	Subsets with Duplication	90	Medium	Link
7	Power Set	1237	Medium	Link
8	Restore IP Addresses	93	Medium	Link
9	Beautiful Arrangement II	667	Medium	Link
10	Increasing Subsequences	491	Medium	Link
11	Permutations	46	Medium	Link
12	Combinations	77	Medium	Link
13	Letter Combinations of a Phone Number	17	Medium	Link
14	Generate Parentheses	22	Medium	Link

// 78. Subsets

// Time: O(n 2^n) | Space: O(n 2^n)
var subsets = function(nums) {
  const result = [];
  const n = nums.length;
  
  // Calculate the total number of subsets
  const totalSubsets = 2 ** n;

  // Generate all subsets
  for (let i = 0; i < totalSubsets; i++) {
    const subset = [];

    // Convert the current subset index to binary
    const binary = i.toString(2).padStart(n, '0');

    // Include the elements whose corresponding bit is set in the binary representation
    for (let j = 0; j < n; j++) {
      if (binary[j] === '1') {
        subset.push(nums[j]);
      }
    }

    result.push(subset);
  }

  return result;    
};

/*
 * 1. The i to n (2^nums.length) in binary represents al possible combinations.
 * 2. 0 to nums.length on every iteration insert only unique combination to subset based on binary '1'.
 * 3. Push all subsets to result.
 */

/*
Subsets. Bitwise Manipulation 
-----------------------------------------------
1. We initialize an empty array result to store all the subsets.
2. We calculate the length of the input array nums and store it in the variable n.
3. We calculate the total number of subsets using totalSubsets = 2 ** n, which is equivalent to Math.pow(2, n).
4. We iterate from 0 to totalSubsets - 1 to generate all the subsets.
5. For each iteration, we create an empty array subset to store the current subset.
6. We convert the current subset index i to binary using i.toString(2).
7. We pad the binary representation with leading zeros to match the length n using padStart(n, '0').
8. We iterate from 0 to n - 1 to check each bit of the binary representation.
9. If the bit is set to '1', we include the corresponding element from the nums array in the current subset.
10. We push the generated subset into the result array.
11. After iterating through all possible subsets, we return the result array.
-----------------------------------------------
Time: O(n 2^n) | Space: O(n 2^n)
*/

// 46. Permutations

// Time: O(n!) | Space: O(n)
var permute = function(nums) {
    const res = [];
    dfs(nums, res, [], []);
    return res;
};

function dfs(nums, result, usedNums, current) {
    // Save finished permutation variant.
    if (current.length === nums.length) {
        result.push([...current]);
        return;
    }
    // Iterate over all nums.
    for (let i = 0; i < nums.length; i++) {
        if (usedNums[i]) {
            continue;
        }
        // Add current num to the permutation arr and mark it as used.
        current.push(nums[i]);
        usedNums[i] = true;
        
        // Go recursively deep with current num as used.
        dfs(nums, result, usedNums, current);

        // Remove current num from the permutation array and from the usedNums.
        current.pop();
        usedNums[i] = false;
    }
}

// 77. Combinations

// Time: O(k n^k) | Space: O(n)
var combine = function(n, k) {
    const result = []; 

    // To go recursively deep building combinations.
    const dfs = (start, combination) => {

        // Once combination is ready.
        if (combination.length === k) {
            result.push([...combination]);
            return;
        }
        // Backtracking logic. Push, call, pop.
        for (let i = start; i <= n; i++) {
            combination.push(i);
            dfs(i + 1, combination);
            combination.pop();
        }
    }
    // Stat from 1 and first empty combination.
    dfs(1, []);
    return result;
};

// 17. Letter Combinations of a Phone Number

// Time: O(n k^n) | Space: O(n k)
var letterCombinations = function(digits) {
    const result = [];
    if (!digits.length) {
        return [];
    }
    // Create chars-digits mapping.
    const digitsMapping = {
        1: [''],
        2: ['a', 'b', 'c'],
        3: ['d', 'e', 'f'],
        4: ['g', 'h', 'i'],
        5: ['j', 'k', 'l'],
        6: ['m', 'n', 'o'],
        7: ['p', 'q', 'r', 's'],
        8: ['t', 'u', 'v'],
        9: ['w', 'x', 'y', 'z'],
    };
    backtrack(0, [], digits, digitsMapping, result);
    return result;
};

function backtrack(index, path, digits, letters, result) {
    // Exit condition.
    if (path.length === digits.length) {
        result.push(path.join(''));
        return;
    }
    // Get the list of letters using the index and digits[index].
    const possibleLetters = letters[digits[index]];
    
    // In case no digit under this index.
    if (!possibleLetters) {
        return;
    }

    for (let i = 0; i < possibleLetters.length; i++) {
        // Add the letter to the path.
        const letter = possibleLetters[i];
        path.push(letter);

        // Move on to the next category.
        backtrack(index + 1, path, digits, letters, result);
        
        // Backtrack by removing the letter before moving onto the next.
        path.pop();
    }
}

/*
 * Backtracking
 * ------------------------------
 * 1. Create char-digit mapping.
 * 2. Backtrack through all possible letters.
 * ------------------------------
 * Time: O(n k^n) | Space: O(n k)
 */

// 22. Generate Parentheses

// Time: O(4^n) | Space: O(n)
var generateParenthesis = function(n) {
    const combinations = [];
    backtrack('(', 1, 0, n, combinations);
    return combinations;
};

/**
 * Helper method generates combinations uses backtracking.
 * @param {string} path 
 * @param {number} openUsed 
 * @param {number} closeUsed 
 * @param {number} n 
 * @param {string[]} combinations 
 */
function backtrack(path, openUsed, closeUsed, n, combinations) {
    // Base case: when we reach 2n length
    if (path.length === 2 * n) {
        // Add path to the list of combination:
        combinations.push(path);
        // Exit from this recursive call.
        return;
    }

    // Case: when we can add more opening bracket:
    // If we haven't used all opening bracket (n pairs = n opens)
    if (openUsed < n) {
        // Add 1 opening, update opening used:
        backtrack(path + '(', openUsed + 1, closeUsed, n, combinations);
    }

    // Case: when we can add more closing bracket:
    // If we have more opening than closing:
    if (openUsed > closeUsed) {
        // Add 1 closing, update closing used:
        backtrack(path + ')', openUsed, closeUsed + 1, n, combinations);
    }
}