Subset Sum Swift

Subset sum Swift

The problem with your approach is that the recursion step does not take into account with how many subsets the current element arr[ptr] can be combined. For example, subsets([1,2]) computes the sum of the subsets {1, 2} and {2}, but omits the subset {1}.

A possible fix for the dynamic programming approach would be to remember not only the sum, but also the count of all subsets starting at a certain position:

func subsets(_ arr: [Int]) -> Int {
    var mem = Array(repeating: (sum: 0, count: 0), count: arr.count)
    return subsetsRecursive(arr, 0, &mem).sum
}

func subsetsRecursive(_ arr: [Int], _ ptr: Int, _ memo : inout [(sum: Int, count: Int)]) -> (sum: Int, count: Int) {
    if (ptr > arr.count - 1) { return (sum: 0, count: 1) }
    if memo[ptr].sum != 0 { return memo[ptr] }
    let res = subsetsRecursive(arr, ptr + 1, &memo)
    memo[ptr] = (2 * res.sum + arr[ptr] * res.count, 2 * res.count)
    return memo[ptr]
}

Examples:

print(subsets([1, 2])) // 6
print(subsets([1, 2, 3])) // 24

This can be simplified further, but hopefully answers your immediate question.

---

An iterative solution would be

func subsetsum(_ arr: [Int]) -> Int {
    var sum = 0
    var count = 1
    for elem in arr {
        sum = 2 * sum + count * elem
        count = 2 * count
    }
    return sum
}

which can be written concisely as

func subsetsum(_ arr: [Int]) -> Int {
    return arr.reduce((sum: 0, count: 1)) {
        (2 * $0.sum + $0.count * $1, 2 * $0.count )
    }.sum
}

---

Alternatively note that each of the n array elements can be in 2^n-1 of the 2ⁿ subsets:

func subsetsum(_ arr: [Int]) -> Int {
    return arr.reduce(0, +) * (1 << (arr.count - 1))
}

Swift - Subarrays of specific length

This a variant of subset sum problem, or more generally, the Knapsack problem. The following solution supposes that:

• All elements of the initial array are strictly positive,
• The initial array may contain repeating elements,
• If a sum can't be reached, the output is an empty array.

Let's starts with an example: let's create a dynamic table in which we'll try to find all the ways to get 5 by adding elements from [1, 2, 3, 4]:

In this table, the rows represent the elements of the array, in an ascending order, plus 0. The columns go from 0 to the sum 5.

In each cell, we ask ourselves, can we get to the title of this column, by adding one or more of the titles of the current and previous rows.

The number of solutions is the count of cells having true in them. In this case, two solutions:

1)

The green cell is true, so the current line is the last element from the solution. In this case, 3 is part of the solution. So the problem of finding a subarray which sum is 5, becomes finding a subarray which sum is 5 - 3. Which is 2. This is represented by the purple arrow 1: Go five columns to the left, and 1 row up.

In arrow 2, we look for the subset that has made it possible to have a partial sum of 2. In this case, we get two thanks to the 2 element. So following arrow 2 we go one row up, and two to the left.

With arrow 3 we reach the first cell in the first column, corresponding to 5 - 3 - 2, which is 0.

2)

Another path we could take starts from the red cell:

As you can see, the problem of making 5 out of [1, 2, 3, 4], becomes a new smaller problem of making 1 from [1, 2, 3], and then 1 out of [1, 2], and finally 1 out of `1.

---

Let's create and fill the dynamic table:

var dynamicTable: [[Bool]] =
    Array(repeating: Array(repeating: false, count: sum + 1),
          count: array.count + 1)

//All of the elements of the first column are true
//since we can always make a zero sum out of not elements
for i in 0...array.count {
    dynamicTable[i][0] = true
}

for row in 1...array.count {
    for column in 1...sum {
        if column < array[row - 1] {
            dynamicTable[row][column] = dynamicTable[row - 1][column]
        } else {
            if dynamicTable[row - 1][column] {
                dynamicTable[row][column] = true
            } else {
                dynamicTable[row][column] = dynamicTable[row - 1][column - array[row - 1]]
            }
        }
    }
}

---

Let's find all the paths leading to the sum:

var solutions = [[Int]]()

func getSubArraysWithTheSum(arr: [Int], row: Int, currentSum: Int, currentSolution: [Int]) {

    //The following block will be executed when
    //we reach the first cell in the first column
    if row == 0,
        currentSum == 0
    {
        solutions.append(currentSolution)
        //notice the return to exit the scope
        return
    }

    //The following block will be executed if
    //the current cell is NOT used to reach the sum
    if dynamicTable[row - 1][currentSum]
    {
        getSubArraysWithTheSum(arr: arr,
                               row: row - 1,
                               currentSum: currentSum,
                               currentSolution: currentSolution)
    }

    //The following block will be executed if
    //the current cell IS used to reach the sum
    if currentSum >= arr[row - 1],
        dynamicTable[row - 1][currentSum - arr[row - 1]]
    {
        getSubArraysWithTheSum(arr: arr,
                               row: row - 1,
                               currentSum: currentSum - arr[row - 1],
                               currentSolution: currentSolution + [arr[row - 1]])
    }
}

---

The whole function looks like this:

func getSubArrays(from array: [Int], withSum sum: Int) -> [[Int]] {

    guard array.allSatisfy({ $0 > 0 }) else {
        fatalError("All the elements of the array must be strictly positive")
    }

    guard array.count > 0, sum > 0 else {
        return []
    }

    var solutions = [[Int]]()
    var dynamicTable: [[Bool]] =
        Array(repeating: Array(repeating: false, count: sum + 1),
              count: array.count + 1)

    //All of the elements of the first column are true
    //since we can always make a zero sum out of not elements
    for i in 0...array.count {
        dynamicTable[i][0] = true
    }

    for row in 1...array.count {
        for column in 1...sum {
            if column < array[row - 1] {
                dynamicTable[row][column] = dynamicTable[row - 1][column]
            } else {
                if dynamicTable[row - 1][column] {
                    dynamicTable[row][column] = true
                } else {
                    dynamicTable[row][column] = dynamicTable[row - 1][column - array[row - 1]]
                }
            }
        }
    }

    func getSubArraysWithTheSum(arr: [Int], row: Int, currentSum: Int, currentSolution: [Int]) {

        //The following block will be executed when
        //we reach the first cell in the first column
        if row == 0,
            currentSum == 0
        {
            solutions.append(currentSolution)
            return
        }

        //The following block will be executed if
        //the current cell is NOT used to reach the sum
        if dynamicTable[row - 1][currentSum]
        {
            getSubArraysWithTheSum(arr: arr,
                                   row: row - 1,
                                   currentSum: currentSum,
                                   currentSolution: currentSolution)
        }

        //The following block will be executed if
        //the current cell IS used to reach the sum
        if currentSum >= arr[row - 1],
            dynamicTable[row - 1][currentSum - arr[row - 1]]
        {
            getSubArraysWithTheSum(arr: arr,
                                   row: row - 1,
                                   currentSum: currentSum - arr[row - 1],
                                   currentSolution: currentSolution + [arr[row - 1]])
        }
    }

    getSubArraysWithTheSum(arr: array, row: array.count , currentSum: sum, currentSolution: [])

    return solutions
}

---

Here are some test cases:

getSubArrays(from: [3, 1, 4, 2], withSum: 5)        //[[3, 2], [4, 1]]
getSubArrays(from: [1, 2, 2, 4], withSum: 3)        //[[2, 1], [2, 1]]
getSubArrays(from: [7, 3, 4, 5, 6, 1], withSum: 9)  //[[5, 3, 1], [5, 4], [6, 3]]
getSubArrays(from: [3], withSum: 3)                 //[[3]]
getSubArrays(from: [5], withSum: 10)                //[]
getSubArrays(from: [1, 2], withSum: 0)              //[]
getSubArrays(from: [], withSum: 4)                  //[]

---

This solution has been inspired by Sumit Ghosh's contribution here. A thorough explanation of how the dynamic table is constructed can be found in this video.

Optimal weights subset sum using backtracking

Here is a possible recursive solution:

// Find the shortest combination of (possibly repeating) numbers in `values`
// whose sum is exactly `target`, and whose count is less than `limit`.
// Return `nil` if no such combination exist.
//
// `target` must be non-negative, and `values` an array of positive
// numbers in decreasing order.
//
func solveHelper(target: Int, values: ArraySlice<Int>, limit: Int) -> [Int]? {
    if target == 0 {
        return [] // Target reached exactly.
    }
    guard let first = values.first else {
        return nil // No values left, target cannot be reached.
    }
    if target/first >= limit {
        return nil // Target cannot be reached with less than `limit` values.
    }

    var best: [Int]? = nil   // Best solution found so far
    var bestCount = limit // Number of values in best solution

    for n in stride(from: target/first, through: 0, by: -1) {
        if let s = solveHelper(target: target - n * first, values: values.dropFirst(), limit: bestCount - n) {
            best = s + repeatElement(first, count: n)
            bestCount = s.count + n
        }
    }

    return best
}

// Find the shortest combination of (possibly repeating) values in `values`
// whose sum is exactly `target`. Return `nil` if no such combination exist.
//
// `target` must be non-negative, and `values` an array of positive
// numbers.
//
func solve(target: Int, values: [Int]) -> [Int]? {
    return solveHelper(target: target, values: ArraySlice(values.sorted(by: >)), limit: Int.max)
}

Examples:

print(solve(target: 1507, values: [2, 7, 20, 70, 200, 700]) as Any)
// Optional([7, 200, 200, 200, 200, 700])

print(solve(target: 1507, values: [20, 70, 200, 700]) as Any)
// nil

print(solve(target: 6, values: [1, 3, 4]) as Any)
// Optional([3, 3])

print(solve(target: 0, values: [1, 3, 4]) as Any)
// Optional([])

Some explanations:

• It is assumed that target is non-negative and that all values
  are positive.
• solve sorts the array in descending order and passes it as an
  ArraySlice to the recursive helper function. This helps to avoid
  further copies of the element storage, when values.dropFirst()
  is passed to the recursive call.
• solveHelper starts “greedy” with the maximal possible number of
  the first (i.e. largest) value, calls itself recursively for the
  remaining target sum and values, then repeats the process with less
  copies of the first value, keeping track of the shortest solution found
  so far.
• In order to “prune” the recursion tree, a limit is passed
  to the recursive call. As an example, if 1507 = 700 + 200 + 200 + 200 + 200 + 7 has already been found then there is no need anymore to sum only values in [2, 7, 20, 70], that would only give longer solutions.
• The function runs reasonably fast in my tests for the given array.
  For a larger number of possible values you probably need a more
  sophisticated algorithm, such as the dynamic programming approach
  described in Change-making problem.

find all subsets that sum to a particular value

def total_subsets_matching_sum(numbers, sum):
    array = [1] + [0] * (sum)
    for current_number in numbers:
        for num in xrange(sum - current_number, -1, -1):
            if array[num]:
                array[num + current_number] += array[num]
    return array[sum]

assert(total_subsets_matching_sum(range(1, 10), 9)       == 8)
assert(total_subsets_matching_sum({1, 3, 2, 5, 4, 9}, 9) == 4)

Explanation

This is one of the classic problems. The idea is to find the number of possible sums with the current number. And its true that, there is exactly one way to bring sum to 0. At the beginning, we have only one number. We start from our target (variable Maximum in the solution) and subtract that number. If it is possible to get a sum of that number (array element corresponding to that number is not zero) then add it to the array element corresponding to the current number. The program would be easier to understand this way

for current_number in numbers:
    for num in xrange(sum, current_number - 1, -1):
        if array[num - current_number]:
            array[num] += array[num - current_number]

When the number is 1, there is only one way in which you can come up with the sum of 1 (1-1 becomes 0 and the element corresponding to 0 is 1). So the array would be like this (remember element zero will have 1)

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]

Now, the second number is 2. We start subtracting 2 from 9 and its not valid (since array element of 7 is zero we skip that) we keep doing this till 3. When its 3, 3 - 2 is 1 and the array element corresponding to 1 is 1 and we add it to the array element of 3. and when its 2, 2 - 2 becomes 0 and we the value corresponding to 0 to array element of 2. After this iteration the array looks like this

[1, 1, 1, 1, 0, 0, 0, 0, 0, 0]

We keep doing this till we process all the numbers and the array after every iteration looks like this

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 2, 1, 1, 1, 0, 0, 0]
[1, 1, 1, 2, 2, 2, 2, 2, 1, 1]
[1, 1, 1, 2, 2, 3, 3, 3, 3, 3]
[1, 1, 1, 2, 2, 3, 4, 4, 4, 5]
[1, 1, 1, 2, 2, 3, 4, 5, 5, 6]
[1, 1, 1, 2, 2, 3, 4, 5, 6, 7]
[1, 1, 1, 2, 2, 3, 4, 5, 6, 8]

After the last iteration, we would have considered all the numbers and the number of ways to get the target would be the array element corresponding to the target value. In our case, Array[9] after the last iteration is 8.

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

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 /h3>

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.

How to extract a subset of a swift 3 Dictionary

Your assumption is correct, there is a more concise/swift-ish way to accomplish what you need.

For example you can do it via reduce, a functional programming concept available in Swift:

let subDict = originalDict.reduce([String: CustomObject]()) {
    guard mySet.contains($1.key) else { return $0 }
    var d = $0
    d[$1.key] = $1.value
    return d
}

Or, in two steps, first filtering the valid elements, and then constructing back the dictionary with the filtered elements:

let filteredDict = originalDict.filter { mySet.contains($0.key) }
    .reduce([CustomObject]()){ var d = $0; d[$1.key]=$1.value; return d }

forEach can also be used to construct the filtered dictionary:

var filteredDict = [CustomObject]()
mySet.forEach { filteredDict[$0] = originalDict[$0] }

, however the result would be good it it would be immutable:

let filteredDict: [String:CustomObject] = { 
    var result = [String:CustomObject]()
    mySet.forEach { filteredDict2[$0] = originalDict[$0] }
    return result
}()

---

Related Topics