Generating Subsets and Permutations
1. Understanding Subset Generation Technique
| Approach | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Recursive Backtracking | Build subsets by including/excluding each element recursively. At each step, make two recursive calls: one including the current element and one excluding it. | O(2^n) |
O(n) |
| Bit Manipulation | Use bitmasks to represent subsets. For a set of size n, iterate from 0 to 2^n - 1. Each bit represents whether an element is included. |
O(n * 2^n) |
O(1) (excluding output space) |
| Iterative | Start with an empty subset. For each element, generate new subsets by appending the element to all existing subsets. | O(2^n) |
O(2^n) |
Example: Recursive Backtracking Implementation
function generateSubsets(nums) {
const result = [];
function backtrack(start, currentSubset) {
result.push([...currentSubset]);
for (let i = start; i < nums.length; i++) {
currentSubset.push(nums[i]);
backtrack(i + 1, currentSubset);
currentSubset.pop();
}
}
backtrack(0, []);
return result;
}
// Example usage:
const nums = [1, 2, 3];
console.log(generateSubsets(nums));
// Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]Example: Bit Manipulation Implementation
function generateSubsets(nums) {
const result = [];
const n = nums.length;
for (let i = 0; i < (1 << n); i++) {
const subset = [];
for (let j = 0; j < n; j++) {
if (i & (1 << j)) {
subset.push(nums[j]);
}
}
result.push(subset);
}
return result;
}
// Example usage:
const nums = [1, 2, 3];
console.log(generateSubsets(nums));
// Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Note: The recursive approach is intuitive and commonly used in interviews. Bit manipulation is efficient for generating all subsets but can be less readable.
2. Generating All Subsets
| Method | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Recursive | Recursively build subsets by including or excluding each element | O(2^n) |
O(2^n) |
| Iterative | Start with empty set, for each element add it to all existing subsets | O(2^n) |
O(2^n) |
| Bit Manipulation | Use bitmasks to represent subset inclusion (0 = exclude, 1 = include) | O(n * 2^n) |
O(2^n) |
Example: Recursive Approach
function generateSubsets(nums) {
const result = [];
function backtrack(start, currentSubset) {
result.push([...currentSubset]);
for (let i = start; i < nums.length; i++) {
currentSubset.push(nums[i]);
backtrack(i + 1, currentSubset);
currentSubset.pop();
}
}
backtrack(0, []);
return result;
}
// Example usage:
const nums = [1, 2, 3];
console.log(generateSubsets(nums));
// Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]Example: Iterative Approach
function generateSubsets(nums) {
let result = [[]];
for (const num of nums) {
const newSubsets = [];
for (const subset of result) {
newSubsets.push([...subset, num]);
}
result = [...result, ...newSubsets];
}
return result;
}
// Example usage:
const nums = [1, 2, 3];
console.log(generateSubsets(nums));
// Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]Example: Bit Manipulation Approach
function generateSubsets(nums) {
const result = [];
const n = nums.length;
for (let i = 0; i < (1 << n); i++) {
const subset = [];
for (let j = 0; j < n; j++) {
if (i & (1 << j)) {
subset.push(nums[j]);
}
}
result.push(subset);
}
return result;
}
// Example usage:
const nums = [1, 2, 3];
console.log(generateSubsets(nums));
// Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]3. Generating Subsets with Duplicates
| Method | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Backtracking with Sorting | Sort the input array first to group duplicates together, then use backtracking with a condition to skip duplicates. | O(2^n) |
O(n) |
| Iterative with Set | Build subsets iteratively, using a set to store unique subsets and avoid duplicates. | O(2^n) |
O(2^n) |
Example: Backtracking with Sorting
function subsetsWithDup(nums) {
nums.sort((a, b) => a - b);
const result = [];
function backtrack(start, path) {
result.push([...path]);
for (let i = start; i < nums.length; i++) {
if (i > start && nums[i] === nums[i - 1]) continue;
path.push(nums[i]);
backtrack(i + 1, path);
path.pop();
}
}
backtrack(0, []);
return result;
}
// Example usage:
const input = [1, 2, 2];
console.log(subsetsWithDup(input));
// Output: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]Example: Iterative with Set
function subsetsWithDup(nums) {
const result = [[]];
const seen = new Set();
for (const num of nums) {
const size = result.length;
for (let i = 0; i < size; i++) {
const subset = [...result[i], num];
const key = subset.join(',');
if (!seen.has(key)) {
seen.add(key);
result.push(subset);
}
}
}
return result;
}
// Example usage:
const input = [1, 2, 2];
console.log(subsetsWithDup(input));
// Output: [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]
Note: When generating subsets with duplicates, the key is to avoid generating duplicate subsets. Sorting helps group duplicates together so they can be skipped during backtracking.
4. Generating All Permutations
| Method | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Backtracking | Recursive approach that builds permutations by choosing one element at a time and backtracking when all elements are used. | O(n! * n) |
O(n) |
| Iterative | Uses a queue or stack to generate permutations iteratively by inserting elements into all possible positions of existing permutations. | O(n! * n) |
O(n! * n) |
| Heap's Algorithm | Efficient algorithm that generates all permutations by swapping elements in a specific order. | O(n!) |
O(1) (excluding recursion stack) |
Example: Backtracking Implementation
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++) {
const num = remaining[i];
current.push(num);
backtrack(current, remaining.filter((_, j) => j !== i));
current.pop();
}
}
backtrack([], nums);
return result;
}
// Example usage:
const input = [1, 2, 3];
console.log(permute(input));
// Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Example: Heap's Algorithm Implementation
function heapsAlgorithm(arr) {
const result = [];
function generate(k, currentArr) {
if (k === 1) {
result.push([...currentArr]);
return;
}
generate(k - 1, currentArr);
for (let i = 0; i < k - 1; i++) {
if (k % 2 === 0) {
[currentArr[i], currentArr[k - 1]] = [currentArr[k - 1], currentArr[i]];
} else {
[currentArr[0], currentArr[k - 1]] = [currentArr[k - 1], currentArr[0]];
}
generate(k - 1, currentArr);
}
}
generate(arr.length, arr);
return result;
}
// Example usage:
const input = [1, 2, 3];
console.log(heapsAlgorithm(input));
// Output: [[1,2,3], [2,1,3], [3,1,2], [1,3,2], [2,3,1], [3,2,1]]
Note: Heap's algorithm is more efficient for generating permutations as it avoids creating new arrays at each step, making it optimal in terms of space complexity.
5. Generating Permutations with Duplicates
| Approach | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Backtracking with Frequency Map | Use a frequency map to track duplicate elements and avoid generating identical permutations. | O(n! * n) |
O(n) |
| Sorting + Visited Array | Sort the array and use a visited array to skip duplicates during backtracking. | O(n! * n) |
O(n) |
Example: Backtracking with Frequency Map
function permuteUnique(nums) {
const result = [];
const freq = {};
for (let num of nums) {
freq[num] = (freq[num] || 0) + 1;
}
function backtrack(current) {
if (current.length === nums.length) {
result.push([...current]);
return;
}
for (let num in freq) {
if (freq[num] > 0) {
current.push(num);
freq[num]--;
backtrack(current);
current.pop();
freq[num]++;
}
}
}
backtrack([]);
return result;
}
// Example usage:
const nums = [1, 1, 2];
console.log(permuteUnique(nums));
// Output: [[1,1,2], [1,2,1], [2,1,1]]
Example: Sorting + Visited Array
function permuteUnique(nums) {
const result = [];
nums.sort(); // Sort to handle duplicates
const visited = 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 (visited[i]) continue;
// Skip duplicates
if (i > 0 && nums[i] === nums[i - 1] && !visited[i - 1]) continue;
visited[i] = true;
current.push(nums[i]);
backtrack(current);
current.pop();
visited[i] = false;
}
}
backtrack([]);
return result;
}
// Example usage:
const nums = [1, 1, 2];
console.log(permuteUnique(nums));
// Output: [[1,1,2], [1,2,1], [2,1,1]]
6. Generating Combinations
| Method | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Recursive Backtracking | Build combinations by including/excluding each element recursively | O(2^n) |
O(n) |
| Iterative with Bit Manipulation | Use bitmasks to represent subset inclusion | O(2^n) |
O(1) |
| Built-in Libraries (e.g., Python itertools) | Use optimized library functions to generate combinations | O(C(n,k)) |
O(1) |
Example: Recursive Backtracking
function generateCombinations(nums, k) {
const result = [];
function backtrack(start, current) {
if (current.length === k) {
result.push([...current]);
return;
}
for (let i = start; i < nums.length; i++) {
current.push(nums[i]);
backtrack(i + 1, current);
current.pop();
}
}
backtrack(0, []);
return result;
}
// Example usage:
const nums = [1, 2, 3];
const combinations = generateCombinations(nums, 2);
console.log(combinations); // [[1,2], [1,3], [2,3]]
Example: Iterative with Bitmask
function generateCombinations(nums, k) {
const result = [];
const n = nums.length;
for (let mask = 0; mask < (1 << n); mask++) {
const combination = [];
let count = 0;
for (let i = 0; i < n; i++) {
if ((mask & (1 << i)) !== 0) {
combination.push(nums[i]);
count++;
}
}
if (count === k) {
result.push(combination);
}
}
return result;
}
// Example usage:
const nums = [1, 2, 3];
const combinations = generateCombinations(nums, 2);
console.log(combinations); // [[1,2], [1,3], [2,3]]
Note: The recursive approach is more intuitive and easier to understand, while the bitmask approach can be faster in some cases due to reduced function call overhead.
7. Generating Letter Case Permutations
| Property | Description | Example |
|---|---|---|
| Input | String containing letters and digits | "a1b2" |
| Output | All possible case permutations of letters in the string | ["a1b2", "A1b2", "a1B2", "A1B2"] |
Example: Generate letter case permutations
function letterCasePermutation(s) {
const result = [];
function backtrack(index, current) {
if (index === s.length) {
result.push(current);
return;
}
const char = s[index];
if (/\d/.test(char)) {
backtrack(index + 1, current + char);
} else {
backtrack(index + 1, current + char.toLowerCase());
backtrack(index + 1, current + char.toUpperCase());
}
}
backtrack(0, "");
return result;
}
console.log(letterCasePermutation("a1b2"));
// Output: ["a1b2", "A1b2", "a1B2", "A1B2"]
Note: For each letter in the string, we generate two branches: one with lowercase and one with uppercase. Digits are added as-is.
8. Generating Balanced Parentheses
| Approach | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Backtracking | Recursively build valid parentheses combinations by ensuring at no point do closing brackets exceed opening brackets. | O(4^n / n^(1/2)) |
O(4^n / n^(1/2)) |
| Dynamic Programming | Build valid combinations using previously computed results for smaller numbers of pairs. | O(4^n / n^(1/2)) |
O(4^n / n^(1/2)) |
| Iterative | Use a stack or queue to generate valid parentheses combinations iteratively. | O(4^n / n^(1/2)) |
O(4^n / n^(1/2)) |
Example: Backtracking Implementation
function generateParentheses(n) {
const result = [];
function backtrack(current, open, close) {
if (current.length === 2 * n) {
result.push(current);
return;
}
if (open < n) {
backtrack(current + '(', open + 1, close);
}
if (close < open) {
backtrack(current + ')', open, close + 1);
}
}
backtrack('', 0, 0);
return result;
}
// Example usage:
console.log(generateParentheses(3));
// Output: ['((()))', '(()())', '(())()', '()(())', '()()()']
Note: The number of valid combinations for
n pairs is the nth Catalan number.
9. Generating Unique BSTs
Generating unique Binary Search Trees (BSTs) involves creating all structurally distinct BSTs that can be formed using a given set of values. This is a classic backtracking and dynamic programming problem.
| Approach | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Recursive with Memoization | For each root value, recursively generate left and right subtrees from remaining values. | O(4^n / n^(3/2)) | O(4^n / n^(3/2)) |
| Catalan Number Based | Use the nth Catalan number to compute the count and generate trees using a recursive approach. | O(4^n / n^(3/2)) | O(4^n / n^(3/2)) |
Example: Generate All Unique BSTs for Values 1 to 3
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function generateTrees(n) {
if (n === 0) return [];
return buildTrees(1, n);
}
function buildTrees(start, end) {
const trees = [];
if (start > end) {
trees.push(null);
return trees;
}
for (let i = start; i <= end; i++) {
const leftTrees = buildTrees(start, i - 1);
const rightTrees = buildTrees(i + 1, end);
for (const left of leftTrees) {
for (const right of rightTrees) {
const root = new TreeNode(i);
root.left = left;
root.right = right;
trees.push(root);
}
}
}
return trees;
}
// Example usage:
const trees = generateTrees(3);
console.log(trees.length); // Output: 5
Note: The number of unique BSTs for n nodes is the nth Catalan number, which can be computed as (2n)! / ((n+1)! * n!).
10. Generating Palindrome Partitions
| Method | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Backtracking | Recursively build partitions by checking if each substring is a palindrome. | O(2^n) |
O(n) |
| Dynamic Programming | Precompute palindromic substrings using DP to optimize partition checks. | O(n^2) |
O(n^2) |
Example: Backtracking Approach
function partition(s) {
const result = [];
backtrack(s, 0, [], result);
return result;
}
function backtrack(s, start, current, result) {
if (start === s.length) {
result.push([...current]);
return;
}
for (let i = start; i < s.length; i++) {
const substr = s.substring(start, i + 1);
if (isPalindrome(substr)) {
current.push(substr);
backtrack(s, i + 1, current, result);
current.pop();
}
}
}
function isPalindrome(str) {
let left = 0, right = str.length - 1;
while (left < right) {
if (str[left++] !== str[right--]) return false;
}
return true;
}
// Example usage:
console.log(partition("aab"));
// Output: [["a","a","b"], ["aa","b"]]
Example: Dynamic Programming Approach
function partitionWithDP(s) {
const n = s.length;
const isPalindrome = Array(n).fill().map(() => Array(n).fill(false));
// Precompute palindromes
for (let i = 0; i < n; i++) {
isPalindrome[i][i] = true;
}
for (let len = 2; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
const j = i + len - 1;
if (s[i] === s[j]) {
if (len === 2 || isPalindrome[i + 1][j - 1]) {
isPalindrome[i][j] = true;
}
}
}
}
const result = [];
dfs(s, 0, [], isPalindrome, result);
return result;
}
function dfs(s, start, current, isPalindrome, result) {
if (start === s.length) {
result.push([...current]);
return;
}
for (let i = start; i < s.length; i++) {
if (isPalindrome[start][i]) {
current.push(s.substring(start, i + 1));
dfs(s, i + 1, current, isPalindrome, result);
current.pop();
}
}
}
// Example usage:
console.log(partitionWithDP("aab"));
// Output: [["a","a","b"], ["aa","b"]]
Note: The backtracking approach explores all possible partitions, while the DP version optimizes palindrome checks using precomputed data.
11. Generating Word Abbreviations
| Property | Description | Example |
|---|---|---|
| abbreviationLength | Maximum length of the abbreviation | 3 |
| includeNumbers | Whether to include numbers in abbreviations | false |
Example: Generate Abbreviations for a Word
function generateAbbreviations(word, maxLength = 3) {
const abbreviations = [];
for (let i = 1; i <= Math.min(maxLength, word.length); i++) {
abbreviations.push(word.substring(0, i));
}
return abbreviations;
}
const word = "algorithm";
console.log(generateAbbreviations(word)); // ["a", "al", "alg"]
Note: Abbreviations are commonly used in technical documentation to simplify long terms.
12. Generating N-Queens Solutions
| Property | Description | Notes |
|---|---|---|
| n | Size of the chessboard (n x n) | Must be a positive integer |
| solutionCount | Number of valid N-Queens solutions | Calculated using backtracking algorithm |
Example: N-Queens Solution for n=4
function solveNQueens(n) {
const board = Array(n).fill().map(() => Array(n).fill(0));
const solutions = [];
function isSafe(row, col) {
for (let i = 0; i < row; i++) {
if (board[i][col] === 1) return false;
if (board[i][col - (row - i)] === 1) return false;
if (board[i][col + (row - i)] === 1) return false;
}
return true;
}
function backtrack(row) {
if (row === n) {
solutions.push(board.map(row => [...row]));
return;
}
for (let col = 0; col < n; col++) {
if (isSafe(row, col)) {
board[row][col] = 1;
backtrack(row + 1);
board[row][col] = 0;
}
}
}
backtrack(0);
return solutions;
}
const solutions = solveNQueens(4);
console.log(solutions.length); // Output: 2
Note: The N-Queens problem is a classic backtracking algorithm example. For n=4, there are exactly 2 distinct solutions.