Find all possible combinations of n numbers in an array which sums to a given value x

Question

Well, I am working on an algorithm.

Where I have to design a function, i.e.

fun returnSums(inputList: List<Int>, targetSum: Int, countOfSummingNumbers: Int) : List<List<Int>> {
      // design your logic here.
}


Test 1 
inputList = [1, 2, 3, 5, 6, 4]
targetSum = 10
countOfSummingNumbers = 3

OutPut List = [[1, 3, 6], [1, 5, 4], [2, 3, 5]]

Explanation: Here output inner lists sums upto 10 which is the target sum, and size of numbers which form this targetSum is 3, which is as required. [6, 4] this also sums to 10, but the size of the list is not as passed in the input. this list should be comprising of 3 numbers not a combination of two.

What I have looked into? I have checked different resources on the internet but could not find anything which resemble this, that when the count of ints in the list is dynamic.

For example, if requirement is to find any pair of two which sums to targetSum. simply looping through would be enough.

If requirement is to find any triplets, I can use three loops, or the two pointers approach to traverse the input list.

But if for example, the count is 100 for a big array, I can't use 100 loops you know. Neither two pointers approach will work.

Also how can this possibly be handled dynamically?

Answer 1

In swift , You can get all possible combinations of giving array like this answer

extension Array {
    var combinationsWithoutRepetition: [[Element]] {
        guard !isEmpty else { return [[]] }
        let arr =  Array(self[1...]).combinationsWithoutRepetition.flatMap { [$0, [self[0]] + $0] }
        return arr
    }
}

Then you can filter that 2d array with what you want like

    let sumArray = inputList.combinationsWithoutRepetition.filter({$0.count == countOfSummingNumbers && $0.reduce(0, +) == targetSum})

All code :

func returnSums(inputList: Array<Int>, targetSum: Int, countOfSummingNumbers: Int) -> [[Int]] {
    let sumArray = inputList.combinationsWithoutRepetition.filter({$0.count == countOfSummingNumbers && $0.reduce(0, +) == targetSum})
    return sumArray
}

var inputList = [1, 2, 3, 5, 6, 4]
var targetSum = 10
var countOfSummingNumbers = 3

print(returnSums(inputList: inputList, targetSum: targetSum, countOfSummingNumbers: countOfSummingNumbers))

extension Array {
    var combinationsWithoutRepetition: [[Element]] {
        guard !isEmpty else { return [[]] }
        let arr =  Array(self[1...]).combinationsWithoutRepetition.flatMap { [$0, [self[0]] + $0] }
        return arr
    }
}

OUTPUT :

[[2, 3, 5], [1, 3, 6], [1, 5, 4]]

Answer 2

Here is my adaptation of a related problem at https://stackoverflow.com/a/64380474/585411. The big difference is that I replaced last_index in the other solution with indexes_by_sum_by_count where indexes_by_sum_by_count[count][sum] gives you all of the indexes into your array where you could reach that sum by that count. Otherwise the explanation there works.

Also note, while this will find all of the answers, there may be a lot of them. This will, at least, quickly ignore past subsets that won't lead to answers.

def subset_sum_iter(array, target, count):
    sign = 1
    array = sorted(array)
    if target < 0:
        array = reversed(array)
        sign = -1
    # Checkpoint A

    indexes_by_sum_by_count = [{} for _ in range(count+1)]
    indexes_by_sum_by_count[0][0] = [-1]

    for i in range(len(array)):
        # We update by descending count so that, eg, i is not
        # yet added to the count 2 dictionary when that is
        # used to update the count 3 dictionary.
        for j in range(count, 0, -1):
            for s in list(indexes_by_sum_by_count[j-1].keys()):
                new_s = s + array[i]
                new_s = s + array[i]
                if 0 < (new_s - target) * sign:
                    pass # Cannot lead to target
                elif new_s in indexes_by_sum_by_count[j]:
                    indexes_by_sum_by_count[j][new_s].append(i)
                else:
                    indexes_by_sum_by_count[j][new_s] = [i]
    # Checkpoint B

    # Now yield up the answers.
    def recur(new_target, max_i, c):
        for i in indexes_by_sum_by_count[c][new_target]:
            if i == -1:
                yield [] # Empty sum.
            elif max_i <= i:
                break # Not our solution.
            else:
                for answer in recur(new_target - array[i], i, c-1):
                    answer.append(array[i])
                    yield answer

    for answer in recur(target, len(array), count):
        yield answer


for ans in subset_sum_iter([1, 2, 3, 5, 6, 4], 10, 3):
    print(ans)

Answer 3

You could obtain a solution in a reasonably-efficient way recursively. Below I present a solution in Ruby, which I've written in "pseudo-code" fashion. That hopefully will allow readers unfamiliar with Ruby to understand the gist of what is being done.

def doit(arr, nbr, target)
  return nil if arr.size < nbr
  find_em(arr.sort_by { |n| -n }, nbr, target)
end

def find_em(arr, nbr, target)
  tot = arr[0,nbr].sum
  return [] if target > tot
  (return tot == target ? [arr] : []) if arr.size == nbr
  # arr.size > nbr
  first, *rest = arr
  a = find_em(rest, nbr, target) 
  if nbr == 1
    if first == target
      b = [[first]]
      a += b
    end
  else
    find_em(rest, nbr-1, target-first).each { |e| a += ([[first] + e]) }
  end
  a
end

---

doit([1, 2, 3, 4, 5], 2, 5)
  #=> [[3, 2], [4, 1]]
doit([1, 2, 3, 5, 6, 4], 3, 10)
  #=> [[5, 3, 2], [5, 4, 1], [6, 3, 1]]

---

Notice that doit sorts arr from largest to smallest and then passes that array to find_it.

I have assumed, without loss of generality, that all element of arr are non-negative. If one or more are initially negative the array can be transformed to an equivalent one in which the array contains all non-negative values. Suppose, for example, one wants arrays of size 3 that total 20 and the smallest value in the array equals -4. In this case we can add 4 to each element of the array (making all elements non-negative) and change the required total from 20 to 32 (20 + 3*4).

To better explain how the recursion works I will execute doit for the first example above after adding puts statements to find_all and including the additional code shown immediately below.

INDENT = 4
def indent; $col += INDENT; end
def undent; $col -= INDENT; end
def pu(s); puts "#{" "*$col}#{s}"; end 
def puhline; pu('-'*([65-$col,1].max)); end

def find_em(arr, nbr, target)
  indent
  puhline    
  pu "arr=#{arr}, nbr=#{nbr}, target=#{target}"
  tot = arr[0,nbr].sum
  pu "tot=#{tot}"
  if target > tot
    pu "returning [] because target > tot"
    a = []
  elsif arr.size == nbr
    a = tot == target ? [arr] : []
    pu "returning #{a} because arr.size == nbr" 
  else
    # arr.size > nbr
    first, *rest = arr
    pu "arr.size > nbr, first = #{first}, rest = #{rest}"
    pu "when not using first call find_em(#{rest}, #{nbr}, #{target})"
    a = find_em(rest, nbr, target) 
    pu "find_em returned a = #{a}"
    if nbr == 1
      pu "nbr = 1"
      if first == target
        pu "first == target"
        b = [[first]]
        pu "b = #{b}"
        a += b
        pu "Now a = a+b = #{a}"
      else
        pu "first != target"
      end
    else
      pu "nbr > 1"
      pu "when using first call find_em(#{rest}, #{nbr-1}, #{target-first})"
      b = find_em(rest, nbr-1, target-first)
      pu "find_em returned b = #{b}"
      b.each { |e| a += ([[first] + e]) }
      pu "Now a = #{a}"
    end
  end
  pu "returning a=#{a}"
  puhline    
  undent
  a
end

---

$col = -INDENT
doit([1, 2, 3, 4, 5], 2, 5)
  #=> [[3, 2], [4, 1]]

displays the following.

---

arr=[5, 4, 3, 2, 1], nbr=2, target=5
tot=9
arr.size > nbr, first = 5, rest = [4, 3, 2, 1]
when not using first call find_em([4, 3, 2, 1], 2, 5)
    -------------------------------------------------------------
    arr=[4, 3, 2, 1], nbr=2, target=5
    tot=7
    arr.size > nbr, first = 4, rest = [3, 2, 1]
    when not using first call find_em([3, 2, 1], 2, 5)
        ---------------------------------------------------------
        arr=[3, 2, 1], nbr=2, target=5
        tot=5
        arr.size > nbr, first = 3, rest = [2, 1]
        when not using first call find_em([2, 1], 2, 5)
            -----------------------------------------------------
            arr=[2, 1], nbr=2, target=5
            tot=3
            returning [] because target > tot
            returning a=[]
            -----------------------------------------------------
        find_em returned a = []
        nbr > 1
        when using first call find_em([2, 1], 1, 2)
            -----------------------------------------------------
            arr=[2, 1], nbr=1, target=2
            tot=2
            arr.size > nbr, first = 2, rest = [1]
            when not using first call find_em([1], 1, 2)
                -------------------------------------------------
                arr=[1], nbr=1, target=2
                tot=1
                returning [] because target > tot
                returning a=[]
                -------------------------------------------------
            find_em returned a = []
            nbr = 1
            first == target
            b = [[2]]
            Now a = a+b = [[2]]
            returning a=[[2]]
            -----------------------------------------------------
        find_em returned b = [[2]]
        Now a = [[3, 2]]
        returning a=[[3, 2]]
        ---------------------------------------------------------
    find_em returned a = [[3, 2]]
    nbr > 1
    when using first call find_em([3, 2, 1], 1, 1)
        ---------------------------------------------------------
        arr=[3, 2, 1], nbr=1, target=1
        tot=3
        arr.size > nbr, first = 3, rest = [2, 1]
        when not using first call find_em([2, 1], 1, 1)
            -----------------------------------------------------
            arr=[2, 1], nbr=1, target=1
            tot=2
            arr.size > nbr, first = 2, rest = [1]
            when not using first call find_em([1], 1, 1)
                -------------------------------------------------
                arr=[1], nbr=1, target=1
                tot=1
                returning [[1]] because arr.size == nbr
                returning a=[[1]]
                -------------------------------------------------
            find_em returned a = [[1]]
            nbr = 1
            first != target
            returning a=[[1]]
            -----------------------------------------------------
        find_em returned a = [[1]]
        nbr = 1
        first != target
        returning a=[[1]]
        ---------------------------------------------------------
    find_em returned b = [[1]]
    Now a = [[3, 2], [4, 1]]
    returning a=[[3, 2], [4, 1]]
    -------------------------------------------------------------
find_em returned a = [[3, 2], [4, 1]]
nbr > 1
when using first call find_em([4, 3, 2, 1], 1, 0)
    -------------------------------------------------------------
    arr=[4, 3, 2, 1], nbr=1, target=0
    tot=4
    arr.size > nbr, first = 4, rest = [3, 2, 1]
    when not using first call find_em([3, 2, 1], 1, 0)
        ---------------------------------------------------------
        arr=[3, 2, 1], nbr=1, target=0
        tot=3
        arr.size > nbr, first = 3, rest = [2, 1]
        when not using first call find_em([2, 1], 1, 0)
            -----------------------------------------------------
            arr=[2, 1], nbr=1, target=0
            tot=2
            arr.size > nbr, first = 2, rest = [1]
            when not using first call find_em([1], 1, 0)
                -------------------------------------------------
                arr=[1], nbr=1, target=0
                tot=1
                returning [] because arr.size == nbr
                returning a=[]
                -------------------------------------------------
            find_em returned a = []
            nbr = 1
            first != target
            returning a=[]
            -----------------------------------------------------
        find_em returned a = []
        nbr = 1
        first != target
        returning a=[]
        ---------------------------------------------------------
    find_em returned a = []
    nbr = 1
    first != target
    returning a=[]
    -------------------------------------------------------------
find_em returned b = []
Now a = [[3, 2], [4, 1]]
returning a=[[3, 2], [4, 1]]
-----------------------------------------------------------------

Note that all values that start in the same column correspond to the same instance of find_all.