Print all Subsequences of a string

Medium

Problem

Print all 2^n subsequences of the string (keep or skip each character, preserving order), including the empty one.

Example 1

Input:  "abc"
Output: "", a, b, c, ab, ac, bc, abc

Also asked as: subsets · print all subsets

Test cases

Case 1

Input:    [1,2,3]
Expected (any order): [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

Case 2

Input:    ["a","b"]
Expected (any order): [[],["a"],["b"],["a","b"]]

Case 3

Input:    []
Expected (any order): [[]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Backtracking (choose / un-choose)

Time O(2ⁿ · n)Space O(n) recursion

At each index, branch: include the element, recurse, then remove it and recurse again.

function subsets(arr) {
const res = [], path = [];
const bt = (start) => {
res.push([...path]);
for (let i = start; i < arr.length; i++) {
path.push(arr[i]);
bt(i + 1);
path.pop();
}
};
bt(0);
return res;
}

2. Bitmask enumeration

Time O(2ⁿ · n)Space O(1) extra

Each subset maps to a number 0..2ⁿ−1; bit j set ⇒ include element j. No recursion.

function subsets(arr) {
const n = arr.length, res = [];
for (let mask = 0; mask < (1 << n); mask++) {
const sub = [];
for (let j = 0; j < n; j++) if (mask & (1 << j)) sub.push(arr[j]);
res.push(sub);
}
return res;
}