[Solved] Given a positive integer N as input, how do I find the product of the numbers in their subsets?

by


Well, there is a very easy and naive recursive solution to retrieving all subsets.

You take away one element from your set, then find all subsets for this new, smaller set. Then you copy the result and add the element you previously removed to the copy. Add the results together and you’re done. For example:

{1,2,3}

Take out 1 and find all subsets of {2,3} giving you:
{{}, {2}, {3}, {2,3}}

Now copy this to give you
A = {{}, {2}, {3}, {2,3}}
B = {{}, {2}, {3}, {2,3}}

Now add 1 to each set in A, giving you
{{1}, {1,2}, {1,3}, {1,2,3}}

combine it with B
{{1}, {1,2}, {1,3}, {1,2,3}, {}, {2}, {3}, {2,3}}

Here’s some code:

function subsets(aSet) {
    if (aSet.isEmpty()) {
        return [theEmptySet]
    }

    let lastElement = aSet.getLast()
    let aSmallerSet = aSet.removeLast()

    let subsetsOfSmallerSet = subsets(aSmallerSet)
    let subsetsContainingLastElement = subsetsOfSmallerSet.map(set => set.insert(lastElement))

    return subsetsOfSmallerSet.concat(subsetsContainingLastElement)
}

I am assuming you mean to get all subsets of the digits of a given number. So, assuming you have split the digits and parsed them back into numbers, then you can just use reduce to get the product.

let digits = //... an array such as [4,0,5]
let subsetsOfDigits = subsets(digits)
subsetsOfDigits.map(subset => subset.reduce((a,b) => a * b))

Ahh, but here you have a problem with the empty set, because you are not passing an initial value to reduce. However, it seems that you’ve ignored the empty set in your example, so you could just filter it out, and then, this code works.

solved Given a positive integer N as input, how do I find the product of the numbers in their subsets?