查找数组中添加到输入数字的所有数字组合 [英] Finding all the number combos in array that add up to input number
问题描述
嘿我正在研究一种算法，该算法采用用户输入的数字，然后通过一个大小为50的数组填充1到100之间的随机数，并查找加到输入的所有数字组合数。
Hey I'm working on figuring out an algorithm that takes a user-entered number and then goes through an array of size 50 filled with random numbers between 1 and 100 and finds all the combinations of numbers that add up to the input number.
例如，给定一个整数数组[3,6,1,9,2,5,12]并传递整数值9，你会返回[ [3,6]，[6,1,2]，[9]，[3,1,5]。在数组中返回结果的顺序无关紧要，尽管你应该返回唯一的集合（即[6,3]和[3,6]是相同的，只返回一个）。此外，个别结果应该按照它们的顺序排列（即[6,1,2]应该返回，而不是[1,2,6]）。
For example, given an array of integers [3,6,1,9,2,5,12] and being passed the integer value 9, you would return [[3,6],[6,1,2],[9],[3,1,5]]. Order of returning the results in the array does not matter, though you should return unique sets (ie. [6,3] and [3,6] are the same and only one should be returned). Also, the individual results should be in the order they are found (ie [6,1,2] should be returned, not [1,2,6]).
当我开始编写代码时，我遇到的第一个解决方案看起来非常低效。我目前正在尝试将每个组合分成它自己的数组，并且每次将一个数字添加到数组时，都会检查数字是否等于输入，是否仍然小于或超过它。它工作不正常，我觉得这可能是一种效率低下的方法：
As I've started writing code, the first solution that I came to seems extremely in-efficient. I'm currently trying to separate each combo into it's own array, and every time a number gets added to the array, a check is done to see if the numbers equal the input, are still less than, or go over it. It's not working properly, and I feel like this might be an inefficient way to do it:
for (int i = 0; i < list.length; i++) {
List<Integer> combo = new ArrayList<Integer>();
int counter = 0;
int current = list[i];
if (current == input){
System.out.println(i);
}
else if (current > input) {
continue;
}
else if (current < input) {
combo.add(current);
if (combo.size() >= 2) {
for (int j = 0; j < combo.size(); j++) {
counter += combo.get(j);
if (counter == input) {
System.out.println("Success");
break;
}
else if (counter < input) {
continue;
}
else if (counter > input) {
break;
}
}
}
}
}
推荐答案
这是一个想法，我没有工作代码。尝试使用递归，测试具有最大可能数量的所有组合以及没有它的所有其余组合。功能如：Sums（Number，maxN），（maxN是我们可以采取的最大数量 - 在第一次调用它是9）
对于你的例子将是：
1.按照建议，对它们进行排序
2.检查maxN是否大于求和的最小值，在你的例子中它是5（在你的集合中不能从小于5的数字中取9 ）;如果它不返回（基本情况）。
3. maxN是否等于tu输入？ （第一次通话中9次）
a）是 - 第一个解决方案子集[9] +总和（数字，dec（maxN））（第一次调用时dec（maxN）将为6）
b）否 - 递归检查'Number - maxN'是否可以根据你的数字中的数字构建，Sums（Number - maxN，dec（K）或'Number - maxN'的最大数量（取决于更小））+ Sums（ Number，dec（maxN）） - 添加其余部分。
This is an idea, I don't have a working code. Try to use recursion, test all combinations with the biggest possible number plus all the rest without it. Function like: Sums(Number, maxN), (maxN is maximum number which we can take - in first call it's 9)
For your example would be:
1. As suggested, sort them and cut bigger than input.
2. Check if the maxN is greater than the minimum required to make a sum, in your example it is 5 (can't make 9 from numbers smaller than 5 in your set); if it's not return (base case).
3. Is maxN equal tu input? (9 in first call)
a) Yes - first solution subset [9] + Sums(Number, dec(maxN)) (dec(maxN) will be 6 in first call)
b) No - recursively check if 'Number - maxN' could be built from numbers from your set, Sums(Number - maxN, dec(K) or max number of 'Number - maxN' (depends what is smaller)) + Sums(Number, dec(maxN)) - add the rest.
这里是仅计算的代码，将数字写成平方和的方法，它通过了HackerRank测试：
Here is code to count only, ways to write a number as sum of squares, it passed HackerRank tests:
import math
def minArgument(x):
s = 0
i = 1
while s < x:
s = s + i * i
i = i + 1
return i - 1
def maxPower(a):
return math.floor(math.sqrt(a))
def sumOfSquares(M, K, cnt):
if M < 1:
return cnt
lowerLimit = minArgument(M)
if K < lowerLimit:
return cnt
else:
if K * K == M:
return sumOfSquares(M, K - 1, cnt + 1)
else:
return sumOfSquares(M, K - 1,sumOfSquares(M - K * K,
min(maxPower(M - K * K), K - 1), cnt))
经过简单的更改后，这将为您提供多种解决方案。我现在看不到如何使用组合构建一个列表作为返回值......
After easy change, this gives you number of solutions. I don't see how to build a list with combinations as a return value now...
这篇关于查找数组中添加到输入数字的所有数字组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
