Print all Subsequences of a string
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): [[]]
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;}