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. So [10, 9, 9, 2] and 20 -> [10, 10] is not valid but [9, 9, 2] is perfectly fine
• Time complexity is not matter (but more efficient solutions will be welcome)
• Any number allowed, including negative numbers.

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.

The last thing I came up with is the algorithm:

1. Find all subsets with the sum of the goal.

2. Find the smallest subset.

Answer 1

Backtracking

The best solution I can think of (by a time complexity point of view) is a backtracking algorithm.

This is very similar to brute force. In the worst case scenario it has the same time complexity of brute force. But it's slightly better because it only check combinations where it make sense.

Theory

We use a recursive visit function to explores the tree of combinations.

Each combination is represented by a path from the root to one leaf.

Until here nothing different from brute force right?

However our function will be smart enough to stop exploring a branch of the tree when the partial solution it has built is equal or greater than the target value (13 in your case).

This little thing makes the Backtraking better than brute force for some inputs.

In the worst case scenario Backtraking will be a slow as brute force.

But there is a problem!

Thanks to @MartinR for pointing out that the current idea does not work with negative numbers.

E.g. Given this array [1, 1, 1, 1, 5, -1] and 4 as target value the algorithm would return [1, 1, 1, 1] as best solution not considering that [5, -1] is indeed better.

Managing negative numbers

In order to manage negative numbers I added the following logic.

If the target value is 0 or positive then the input array is sorted with ascending order (negative numbers will be put first).

So [1, 1, 1, 1, 5, -1] will become [-1, 1, 1, 1, 1, 5].

Otherwise if target is negative then the input array will be sorted with descending order.

So [1, 1, 1, 1, 5, -1] will become [5, 1, 1, 1, 1, -1].

Coding 💻💻💻

The Swift solution is made of 4 parts

1. The SolutionHasNotExceededTarget typealias
2. The ArrayWithSum struct
3. The smallestSubset(of:whereSumIs:) function
4. The visit(solution:unusedElms:target:solutionHasNotExceededTarget:) function

1. SolutionHasNotExceededTarget

I need a closure to check if the current solution has exceeded the target.

This depends on the sign of the target.

If the target is non negative than the input array is sorted in ascending order and then the current solution must never be greater than the target.

On the other hand if the target is negative, the array is sorted in descending order and then the current solution must never be less than the target.

So to recap, in case of negative target this closure will be

$0 > $1

It means that if the sum of the current solution is greater than the target it's ok because (being the target negative) we could find negative numbers later as we go deeper in the tree.

Otherwise if the target is non negative, the closure will be

$0 < $1

This is the type definition of such a closure.

typealias SolutionHasNotExceededTarget = (Int, Int) -> Bool

2. ArrayWithSum

The code will need to calculate the sum of all the integers into an array a lot of times. This operation has Time Complexity O(m) where m is the length of the array. I don't want to waste time calculating the same value multiple times so I'll define a wrapper for Array of Int in order to store the sum of its elements.

struct ArrayWithSum: Comparable {

    static let empty = ArrayWithSum([])
    let array: [Int]
    let sum: Int

    init(_ array: [Int]) {
        self.array = array
        self.sum = array.reduce(0, +)
    }

    private init(arrayWithSum: ArrayWithSum, elm: Int) {
        self.array = arrayWithSum.array + [elm]
        self.sum = arrayWithSum.sum + elm
    }

    func appending(elm: Int) -> ArrayWithSum {
        return ArrayWithSum(arrayWithSum: self, elm: elm)
    }

    static func < (lhs: ArrayWithSum, rhs: ArrayWithSum) -> Bool {
        lhs.array.count < rhs.array.count
    }

}

As you can see the wrapper conforms to Comparable which will make easy to compare 2 solutions when looking for the best one.

3. smallestSubset(of:whereSumIs:)

This function will prepare the data for the vist function.

func smallestSubset(of nums: [Int], whereSumIs target: Int) -> [Int]? {

    let sorting: SolutionHasNotExceededTarget = target > 0
        ? { $0 < $1 }
        : { $0 > $1 }

    let sortedNums = nums.sorted(by: sorting)

    return visit(solution: .empty,
                 unusedElms: sortedNums,
                 target: target,
                 solutionHasNotExceededTarget: sorting)?.array
}

It sorts the array with ascending order if the target is non negative. And with descending order if the target is negative.

4. visit(solution:unusedElms:target:solutionHasNotExceededTarget:)

Finally the visit function which applies the backtracking logic discussed earlier.

func visit(solution: ArrayWithSum,
           unusedElms: [Int],
           target: Int,
           solutionHasNotExceededTarget: SolutionHasNotExceededTarget) -> ArrayWithSum? {

    if solution.sum == target {
        return solution
    }

    guard solutionHasNotExceededTarget(solution.sum, target) else {
        return nil
    }


    return unusedElms
        .enumerated()
        .map { (offset, elm) in
            var unusedElms = unusedElms
            unusedElms.remove(at: offset)
            return visit(solution: solution.appending(elm: elm),
                         unusedElms: unusedElms,
                         target: target,
                         solutionHasNotExceededTarget: solutionHasNotExceededTarget)
        }
        .compactMap { $0 }
        .min()
}

Test

Let's run some tests

smallestSubset(of: [1, 9, 2, 5, 3, 10], whereSumIs: 13)
> [3, 10]

smallestSubset(of: [1, 1, 1, 1, 5, -1], whereSumIs: 4)
> [-1, 5]

smallestSubset(of: [-1, 2, 10, 1, -1, -3, 5, -15], whereSumIs: -5)
> [10, -15]

smallestSubset(of: [-50, 2, 10, 1, -1, -3, 5, -5], whereSumIs: -5)
> [-5]

smallestSubset(of: [10, 9, 9, 2], whereSumIs: 20)
> [2, 9, 9]

Space complexity

Memory wise, in the worst case scenario we will have as many opened recursive calls as the height of the tree.

The height of the three is equals to the number of elements in the input array so.

Furthermore rach recursive call needs space proportionally to the length of the input array so.

Space complexity = O(n) * O(n) = O(n^2)

Where n is the number of elements in the input array.

Time complexity

As said before, in the worst case scenario the function will check every possible combination. In other words every node of the tree will be visited.

Time complexity: O(2^n)

Where n is the number of elements in the input array.

Answer 2

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:

validSubsets.reduce(array) { $0.count < $1.count ? $0 : $1 }

Wrap it up in a function will be:

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 }
}

_{Note that I think it is not very efficient and it would be nice if someone can calculate the time complexity but since the question mentioned that complexity is not matter, it is a valid solution.}