Find minimum count of items where sum of them is X from an array

Question

I recently faced an interview question where you have to find minimum needed items from an array that can added together to generate X value.

For example giving:

[1, 9, 2, 5, 3, 10] and the goal is: 13, => it should be [10, 3]

• You can't use any number out side of array.

I have tried to sort items and take from the head one by one and some other stuff, but no lucks. Although, I have solved this by a not really performant solution and I will post it as an answer. I am looking for a more performant solution.

Solution:

First we have to find all subsets of the array:

extension Array {
    var allSubsets: [[Element]] {
        guard count > 0 else { return [[]] }

        let tail = Array(self[1..<endIndex])
        let head = self[0]
        let withoutHead = tail.allSubsets

        let withHead = withoutHead.map { $0 + [head] }

        return withHead + withoutHead
    }
}

Then we can filter all subsets that their sum is equal to the goal like:

subsets.filter { $0.reduce(0) { $0 + $1 } == goal }

And lastly, find the smallest subset by its count:

func minimumElements(in array: [Int], goal: Int) -> [Int] {
    let subsets = array.allSubsets
    
    let validSubsets = subsets.filter { subset in
        subset.reduce(0) { $0 + $1 } == goal
    }
    
    return validSubsets.reduce(array) { $0.count < $1.count ? $0 : $1 }
}

_{This question was originally asked and answered in StackOverflow but moved here as suggestion.}

Answer 1

Naming

Your function does not return “minimum elements,” but the shortest subset of an array with a given sum. I would suggest something like

func shortestSubset(of array: [Int], withSum goal: Int) -> [Int]

Handling exceptional cases

Your code returns the entire array if no subset with the given sum exists, which seems not sensible to me.

In a comment you said that it should return an empty array in that case, but that would be ambiguous: an empty array is also the correct result for goal = 0.

The Swift way would be to make the result an optional which is nil if no subset is found:

func shortestSubset(of array: [Int], withSum goal: Int) -> [Int]? {
    let subsets = array.allSubsets

    let validSubsets = subsets.filter { subset in
        subset.reduce(0, +) == goal
    }

    if let firstValid = validSubsets.first {
        return validSubsets.dropFirst().reduce(firstValid) { $0.count < $1.count ? $0 : $1 }
    } else {
        return nil
    }
}

Note also that the + operator can be passed directly to the closure parameter of reduce() which reduces(!) the code slightly.

Performance: avoid creation of intermediate arrays

The first performance problem is that a list with all subsets is generated first. For an array with \$ N \$ elements that makes \$ 2^N \$ subsets.

A better approach would be to determine the shortest subset while enumerating the subsets, instead of putting all subsets into a list first. Here is a first attempt:

// Version A:

func shortestSubset(of array: [Int], withSum goal: Int) -> [Int]? {
    // Terminating condition:
    guard let first = array.first else {
        return goal == 0 ? [] : nil
    }

    // Recursion:
    let tail = Array(array.dropFirst())
    let subsetWithout = shortestSubset(of: tail, withSum: goal)
    let subsetWith = shortestSubset(of: tail, withSum: goal - first)

    switch (subsetWithout, subsetWith) {
    case (let s1?, let s2?): return s1.count < s2.count + 1 ? s1 : [first] + s2
    case (let s1?, nil): return s1
    case (nil, let s2?): return [first] + s2
    case (nil, nil): return nil
    }
}

In the recursion step, the shortest subsets which can be obtained by including or omitting the first array element are determined recursively. The switch-statement is used to handle the case where none, one, or both of these intermediate results are nil.

This turned to be a bit faster in my tests, but there are still many intermediate array created at

let tail = Array(array.dropFirst())

If we modify the method to take a collection of integers instead of an array then we can pass the slice array.dropFirst() directly to the recursive call. Slices are “cheap” to create and share the storage with their origin (unless mutated):

// Version B:

func shortestSubset<C: Collection>(of array: C, withSum goal: Int) -> [Int]? where C.Element == Int {
    // Terminating condition:
    guard let first = array.first else {
        return goal == 0 ? [] : nil
    }

    // Recursion:
    let subsetWithout = shortestSubset(of: array.dropFirst(), withSum: goal)
    let subsetWith = shortestSubset(of: array.dropFirst(), withSum: goal - first)
    switch (subsetWithout, subsetWith) {
    case (let s1?, let s2?):
        return s1.count < s2.count + 1 ? s1 : [first] + s2
    case (let s1?, nil):
        return s1
    case (nil, let s2?):
        return [first] + s2
    case (nil, nil):
        return nil
    }
}

This turned out to be considerably faster in my test.

Performance: prune the search tree

A possible performance improvement is to stop the recursion if the goal cannot be reached with the remaining array elements, i.e. if the target sum is smaller than the smallest possible sum or larger than the largets possible sum of the array.

Here it is useful to do the recursion in a helper function. The main function computes the smallest and largest sum once and passes it on to the helper function. The helper function can update those limits, without the need of computing them again.

The helper function takes an array slice as argument, that is another way to void the creation of intermediate arrays.

// Version C:

func shortestSubsetHelper(of array: ArraySlice<Int>, withSum goal: Int,
                          min: Int, max: Int) -> [Int]? {
    guard let first = array.first else {
        return goal == 0 ? [] : nil
    }
    if goal < min || goal > max {
        return nil
    }
    let subsetWithout = shortestSubsetHelper(of: array.dropFirst(), withSum: goal,
                                         min: min, max: max)
    let subsetWith = first < 0 ?
        shortestSubsetHelper(of: array.dropFirst(), withSum: goal - first,
                              min: min - first, max: max) :
        shortestSubsetHelper(of: array.dropFirst(), withSum: goal - first,
                              min: min, max: max - first)
    switch (subsetWithout, subsetWith) {
    case (let s1?, let s2?):
        return s1.count < s2.count + 1 ? s1 : [first] + s2
    case (let s1?, nil):
        return s1
    case (nil, let s2?):
        return [first] + s2
    case (nil, nil):
        return nil
    }
}

func shortestSubset(of array: [Int], withSum goal: Int) -> [Int]? {

    let smallestSum = array.filter { $0 < 0 }.reduce(0, +)
    let largestSum = array.filter { $0 > 0 }.reduce(0, +)
    return shortestSubsetHelper(of: array[...], withSum: goal,
                                min: smallestSum, max: largestSum)
}

Dynamic programming

What we have here is a variant of the “subset sum problem”, which has well-known solutions using dynamic programming. Instead of determining only if a subset with the given sum exists we also need the smallest subset with that sum.

The following is motivated by the “Pseudo-polynomial time dynamic programming solution” from the above Wikipedia article. We maintain a dictionary which for every achievable sum stores the shortest subset with that sum that has been found so far. The given array is traversed once, and the dictionary updated accordingly for each array element.

// Version D:

func shortestSubset(of array: [Int], withSum goal: Int) -> [Int]? {
    // Map each possible sum to the shortest subset found so far with that sum:
    var dp: [Int: [Int]] = [0: []]

    for elem in array {
        let upd = dp.map { (key, value) in (key + elem, value + [elem])}
        for (key, value) in upd {
            if let oldValue = dp[key] {
                if value.count < oldValue.count {
                    dp[key] = value
                }
            } else {
                dp[key] = value
            }
        }
    }
    return dp[goal]
}

This turned out to be faster for large arrays.

Benchmarks

The following (very simple) benchmark was done on a 3.5 GHz Quad-Core Intel Core i5 iMac running macOS 10.15, and

let array = [1, -2, 3, -4, 5, -6, 100, 100, 7, -8, 9, -10, 11, -12]
let goal = 20

let start = Date()
let result = shortestSubset(of: array, withSum: goal)
let end = Date()
print(result, end.timeIntervalSince(start) * 1000)

compiled with Xcode 11.3.1 in Release mode, i.e. with optimization.

Results (approximately):

• Original code: 6 milliseconds.
• Version A: 3 milliseconds.
• Version B: 0.7 milliseconds.
• Version C: 0.2 milliseconds.
• Version D: 0.4 milliseconds.

With the larger array

let array = [1, -2, 3, -4, 5, -6, 100, 100, 7, -8, 9, -10, 11, -12,
             1, -2, 3, -4, 5, -6, 100, 100, 7, -8, 9, -10, 11, -12]
let goal = 20

we get the following results:

• Original code: ???
• Version A: 37733 milliseconds.
• Version B: 6079 milliseconds.
• Version C: 548 milliseconds.
• Version D: 2.5 milliseconds.