1

Question is basically to generate all subsets given an array of unique integers.

For example powerSet[1,2,3] should return [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

Here is my recursive attempt:

function powerset(array) {
  // Write your code here.
    let set = [[]];
    powersetHelper(array, [], set);
    return set;
}

function powersetHelper(array, subset, set) {
    if (array.length === 0) return;
    for (let i = 0; i < array.length; i++) {
        subset.push(array[i]);
        set.push(subset);
    }
    let newArr = array.slice(1);
    powersetHelper(newArr, [], set)
}

Why is this returning [[], [1, 2, 3], [1, 2, 3], [1, 2, 3], [2, 3], [2, 3], [3]] instead of the correct solution?

Additionally, I have attempted this iteratively as follows:

function powerset(array) {
  // Write your code here.
    let subset = [];
    let set = [[]];
    while (array.length > 0) {
        for (let j = 0; j < array.length; j++) {
            let num = array[j];
            subset.push(num);
            set.push(subset);
        }
        array = array.slice(1);
    }
    return set;
}

This is also incorrect and somehow returning what I have below even though it seems to be the same logic as my recursive solution

[
  [],
  [1, 2, 3, 2, 3, 3],
  [1, 2, 3, 2, 3, 3],
  [1, 2, 3, 2, 3, 3],
  [1, 2, 3, 2, 3, 3],
  [1, 2, 3, 2, 3, 3],
  [1, 2, 3, 2, 3, 3]
]
Kushh
  • 99
  • 1
  • 7

1 Answers1

3

You need to take a copy without object reference.

function powerSet(array) {
    // Write your code here.
    let set = [[]];
    powersetHelper(array, [], set);
    return set;
}

function powersetHelper(array, subset, set) {
    if (array.length === 0) return;
    for (let i = 0; i < array.length; i++) {
        subset.push(array[i]);
        set.push([...subset]); // take copy without object reference
    }
    let newArr = array.slice(1);
    powersetHelper(newArr, [], set)
}

console.log(powerSet([1, 2, 3])); // [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
.as-console-wrapper { max-height: 100% !important; top: 0; }

Second one, with the same problem

function powerSet(array) {
    // Write your code here.
    let subset = [];
    let set = [[]];
    while (array.length > 0) {
        for (let j = 0; j < array.length; j++) {
            let num = array[j];
            subset.push(num);
            set.push([...subset]);
        }
        array = array.slice(1);
    }
    return set;
}

console.log(powerSet([1, 2, 3])); // [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
.as-console-wrapper { max-height: 100% !important; top: 0; }
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
  • 3
    Both outputs are still wrong :) – OPTIMUS PRIME Sep 07 '20 at 21:07
  • I figured it out using this same logic. You are right, I was pushing a reference to subset into the set which does not work. I have to push that actual subset in that moment of time, and not allow it to be changed. I have included my working solution in an edit above which is very similar to yours (I just slice it to make a copy instead of spread operator) – Kushh Sep 07 '20 at 21:20
  • 2
    Actually, this solution is still wrong because it does not actually get the [1,3] case – Kushh Sep 07 '20 at 21:24