查找数组中的所有数字组合，加起来输入数字

嘿，我正在研究一个算法，它需要用户输入的数字，然后通过一个大小为50的数组，填充1到100之间的随机数并找到加起来到输入数字的所有数字组合。例如，给定一个整数数组[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 (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; 
      }     
      } 
     } 
     } 
    }

来源

2016-08-20 Spance

如果我们应该忽略代码的某些部分，为什么包括这些部分呢？不是说它是不可读的，但这仍然是不必要的 – Dici

当然，我继续并将它们取出 – Spance

该算法必须是低效率的，因为它是Subset Sum问题的变体：https：//en.wikipedia.org/wiki/Subset_sum_problem – mszymborski

这是一个想法，我没有一个工作代码。尝试使用递归，测试所有组合的最大可能数量加上所有其余的没有它。函数如：Sums（Number，maxN），（maxN是我们可以使用的最大数字 - 在第一次调用时为9）对于您的示例应该是：
1.按照建议对它们进行排序并剪切大于输入。
2.检查maxN是否大于求和所需的最小值，在你的例子中它是5（不能使9中的数字小于5）。如果不是返回（基本情况）。
3.是否maxN等于tu输入？（第一次通话中有9个）
a）是 - 第一个解决方案子集[9] +和（数量，dec（maxN））（dec（maxN）将在第一次通话中为6）
b）否 - 递归检查'数量 - maxN'可以从你的集合中的数字来构建，Sums（Number - maxN，dec（K）或者'Number - maxN'的最大数量（取决于哪个更小））+ Sums（Number，dec（maxN）） - 添加其余的。

这里是代码只算，方法写一个数字作为平方和，它通过HackerRank测试：

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

轻易地变更后，这给你的解决方案的数量。我不明白如何建立一个组合列表作为返回值现在...

来源

2016-08-21 01:02:20

查找数组中的所有数字组合，加起来输入数字

回答

相关问题