I have a large array of integers (~3k items), and I want to find the indices of every combination of numbers where the sum of said numbers is equal to X. How to do this without the program taking years to execute?

I can find the first combination possible with the following Python code:

def find_numbers_that_sum_to(source_arr, target_number, return_index=True):
    result = []
    result_indices = []
    
    for idx, item in enumerate(source_arr):
        sum_list = sum(result)
        
        assert (sum_list   item) <= target_number
        result.append(item)
        result_indices.append(idx)
        
        if (sum_list   item) == target_number:
            break
    
    return result_indices

But I need every combination possible. At least a way of generating them dynamically. I only ever need one of them at a time, but if the indices it gave me don't match another criteria I need, I'll need the next set.

CodePudding user response：

One efficient way to do it is with the "two-pointers approach"

def find_numbers_that_sum_to(arr, target_number):
    arr.sort() # sort the array in ascending order
    start = 0
    end = len(arr) - 1
    result = []
    while start < end:
        curr_sum = arr[start]   arr[end]
        if curr_sum == target_number:
            result.append((start, end))
            start  = 1
            end -= 1
        elif curr_sum < target_number:
            start  = 1
        else:
            end -= 1
    return result

find_numbers_that_sum_to(source_arr, target_number)

CodePudding user response：

Unfortunately, this problem is NP-hard, meaning that there's no currently known polynomial time algorithm for this. If you want to benchmark your current code against other implementations, this SO question contains a bunch. Those implementations may be faster, but their runtimes will still be exponential.