Find possible sums given an array of numbers?

Do you mean :

- you have an array of variable lenth ex: [3, 7, 12 ]

- and you want to compute all the possible sums :

0, 3, 7, 12, 3+7, 3+12, 7+12, 3+7+12

Yes, that's what I mean. Sorry if I wasn't clear!

Well.

I did not write the full code, but here is a way to do it;

The principle is to compute all the sum combinations :

a combination can be represented by a binary word, where digit is 1 is the number is in combination, 0 otrherwise

For instance, the combination with the first 3 numbers is 11100000

Hence the idea for the algorithm, where I give you the steps

1. let n = myArray.count // Number of elements in array

2. compute N = 2**n (2 to power n) eg if N = 8, 2**8 = 256

func powerOf2(p: Int) -> Int { // Of course, this could be made much more generic and genarl

result = 1

for i in 0..<p { result *= 2 }

return p

}

N = powerOf2(n)

3. Define a set mySetOfResults to hold the results

let mySetOfResults : Set<Int> = [] // assuming you want Int, but could be any type of numbers

4. Define an Array, to transform the binary into an array of Bool

binaryCombi = Array(count: n, repeatedValue: false) // all set to false

5. Loop through all possible combinations, by getting an index varying from 0 to N (all the possible binary numbers in between will be used, hence all combinations) :

for combi in 0..<N {

populate binaryCombi // see point 6

compute the sum for the combination // see point 7

write the sum in mySetOfResults // see point 8

}

6. To populate binaryCombi

var remain = N

for i in 0..<n {

binaryCombi[i] = (remain % 2 == 1) // If there is a 1, it's true

remain /= 2 // next digit to the left

}

7. To compute the sum, add all numbers i, where binaryCombi[i] is true

var sum = 0

for i in 0..<n {

if binaryCombi[i] { sum += myArray[i]

}

8. To write the sum

mySetOfResults.insert(sum)

9. You can now print the set, reorder it…

Okay, I'm going to give this a shot--will let you know how it goes. Thank you for taking the time to outline that for me!

Yes, tell if it answered your question. Of course, this can be optimized for performance if you need.

let numbers = [1,2,3,4]

let n = Double(numbers.count)

let powerOfTwo = Int(pow(2.0, n))

var mySetOfResults: Set<Int> = []

var binaryCombi = Array(count: Int(n), repeatedValue: false)

var remain = powerOfTwo



for combi in 0..<powerOfTwo {

    for i in 0..<Int(n) {
        binaryCombi[i] = (remain % 2 == 1)
        remain /= 2
    }
   
    var sum = 0
   
    for i in 0..<Int(n) {
        if binaryCombi[i] {
            sum += numbers[i]
           
        }
    }
   
    mySetOfResults.insert(sum)
}

print(mySetOfResults)

I'm not sure where the values are being set from false to true. This is what I've got so far --

Hi. Here is a simple recursive solution.

func sums(values: [Int]) -> [Int] {
    var mutableValues = values
    guard let lastValue = mutableValues.popLast() else {
        return [0]
    }
    let precedingSums = sums(mutableValues)
    return precedingSums + precedingSums.map(){ $0 + lastValue }
}


print(sums([]))                                 // prints [0]
print(sums([0]))                                // prints [0, 0]
print(sums([3]))                                // prints [0, 3]
print(sums([2, 5]))                             // prints [0, 2, 5, 7]
print(sums([1, 10, 100]))                       // prints [0, 1, 10, 11, 100, 101, 110, 111]


print(sums([1, 1, 1]))                          // prints [0, 1, 1, 2, 1, 2, 2, 3]
print(Set(sums([1, 1, 1])).sort())              // prints [0, 1, 2, 3]
print(Set(sums([1, 1, 1])).sort().dropFirst())  // prints [1, 2, 3]

You missed line 10 to initialize properly remain.

The values of binaryCombi are set to true (for the relevant bit) on line 12.

var str = "Hello, playground"
let numbers = [1,2,3,4]
let n = Double(numbers.count)
let powerOfTwo = Int(pow(2.0, n))
var mySetOfResults: Set<Int> = []
var binaryCombi = Array(count: Int(n), repeatedValue: false)
var remain : Int

for combi in 0..<powerOfTwo {
    remain = combi
    for i in 0..<Int(n) {
        binaryCombi[i] = (remain % 2 == 1)
        remain /= 2
    }
   
    var sum = 0
   
    for i in 0..<Int(n) {
        if binaryCombi[i] {
            sum += numbers[i]
           
        }
    }
   
    mySetOfResults.insert(sum)
}
print(mySetOfResults.sort())