Problem

Generate ALL possible subsets of a given set. The set is given in the form of a string s containing distinct lowercase characters ‘a’ – ‘z’.

Example

{
"s": "xy"
}

Output:

["", "x", "y", "xy"]

Solution

function subset(inputStr) {
    let allsubset = [""];

    for (let i = 1; i <= inputStr.length; i++) {
        let old_len = allsubset.length;
        for (let j = 0; j < old_len; j++) {
            // Note that we are doing push that is adding value at the end of array, so we already have the old values stored in it.
            allsubset.push(allsubset[j] + inputStr[i - 1]);
        }
    }
    return allsubset;
}

subset("xy");

Time and Space Complexity

Time: O(2^n * n).
Auxiliary space: O(2^n * n).
Total space: O(2^n * n).