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

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?

CodePudding user response：

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

CodePudding user response：

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)