确定列表中哪些数字是给定数字之和的算法 [英] Algorithm to determine which numbers in a list are the sum of a given number

问题描述

我有一个编码问题，我想解决.我还没有想出一个好的算法.

I have a coding question that I am try to solve. I haven't been able to come up with a good algorithm yet.

给出数字X(例如200)，确定列表中的哪些数字(例如:4,5,10、10、23,67,889、150、50)相加时将等于X.在这种情况下答案是(50，150).到目前为止，我考虑过先对列表进行排序(从最低到最高)，然后循环添加数字直到获得大于X的值.丢弃列表中所有剩余的数字，因为不需要它们(例如889).现在，我有了产生200之和所需的数字列表.现在，我需要确定哪些数字总和为200.

Given a number X (e.g. 200), determine which numbers from a list (e.g.: 4,5,10, 10, 23,67,889, 150, 50) will when summed up will be equal to X. In this case the answer is (50, 150). So far I thought about first sorting the the list (lowest to highest) then loop through adding the numbers until I get to a value greater than X. Discard all the remaining numbers in the list since they are not needed (e.g. 889). Now I have the list of numbers required to produce a sum of 200. Now I need to determine which are the numbers that sum up to 200.

目前停留在这一点.

任何想法都非常感谢.

推荐答案

取决于.如果想要快速，可以使用贪婪算法:(伪代码)

Depends. If you want it fast, you can use a greedy(ish) algorithm: (pseudo code)

n = answer; // what you want the numbers to add up to be. 
numbers = [1, 2, 40, 39,....]; //the candidates. 
addList = Array[][];
addList[0] = numbers;
level = 0;
while(true){
    for (number in numbers){
         currnum = addlist[level][i] + number;
         if(currnum == n){
             return true; // or what ever you want to return
         } else if (currnum < n){
              addlist[level+1].append(currnum);
         }
    }
    if (addlist[level+1].length ==0){
          return false; // it will never add up to the value n. 
    }
    level++;
}

这是严格的伪代码，我只是为了便于阅读而将arraylist和array混合在一起.

This is strictly pseudo code, I'm mixing arraylist and array a bit just for readability.

这篇关于确定列表中哪些数字是给定数字之和的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！