Java 查找数组中所有加起来等于特定数字的组合

Question

我目前正在研究面试书中的以下问题：

You are given a random array of 50 unique integers ranging from 1 to 100 inclusive. Write a method using Java that takes in a positive integer as a parameter and returns an array of all the number combinations that add up to that value.

例如，给定一个整数数组 [3,6,1,9,2,5,12] 并传递整数值 9，您将 return [[3,6], [6,1,2],[9],[3,1,5]]。 returning 数组中结果的顺序并不重要，尽管你应该 return 独特的集合（即 [6,3] 和 [3,6] 是相同的，只有一个应该是 returned）。此外，各个结果应该按照它们被发现的顺序排列（即 [6,1,2] 应该 returned，而不是 [1,2,6]）。

我在这方面取得了不错的进展，但我担心我可能会以错误的方式解决这个问题。

import java.util.*;


public class findCombinations {
  public static void main(String[] args) {
    int number;
    int[] list = new int[10];
    Scanner reader = new Scanner(System.in);

    //fill the array
    for (int i = 0; i < list.length; i++) {
      number = (int)(Math.random() * 10) + 1;
      list[i] = number;
      for (int j = 0; j < i; j++) { //remove duplicates
        if (list[i] == list[j]) {
          i--;
          break;
        }
      }
    }

    Arrays.sort(list);

    //test output
    for (int i = 0; i < list.length; i++) {
      System.out.println(list[i]);
    }
    System.out.println("Enter a number: ");
    int input = reader.nextInt(); 
    ArrayList<Integer> trimmedList = new ArrayList<Integer>();

    //cut out the numbers that are impossible to use
    for (int i = 0; i < list.length; i++) {
      if (list[i] <= input) {
        trimmedList.add(list[i]);
      }
    }
    //test output
    printList(trimmedList);

    ArrayList<Integer> comboList = new ArrayList<Integer>();
    System.out.println("Finding combinations...");

    for (int i = 0; i < trimmedList.size(); i++) {
      int current = trimmedList.get(i);
      if (current == input) { System.out.println(current); }
      else if (current < input) {
        comboList.add(current);
        if (isCombo(comboList, input)) {
          printList(comboList);
        }
        else { continue; }
      }
      else { continue; }
    }
  }

  public static boolean isCombo(ArrayList<Integer> list, int input) {
    ArrayList<Integer> combo = new ArrayList<Integer>();
    int sum = 0;

    for (int i : list)
      sum += i;

    if (sum == input) { return true; }
    else { return false; }
  }

  public static void printList(ArrayList<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
      System.out.print(list.get(i));
    }
  }
 }

我知道这是不完整的，但我想问问是否有人对此有任何建议或改进？我整理了我的列表并删除了所有可能不会被使用的整数，但现在困难的部分是找到所有的组合。

Answer 1

由于这是一个学习练习，如果您能自己解决这个问题，您将受益最大。所以...

提示：

数字先排序是对的
我会使用递归来迭代解决方案。给定一个部分和，只有小于一定数量的数字才有可能被添加到总和中......
>在<开始编写代码之前，先在头脑中制定出算法。

我同意@nbrooks 关于面试官正在寻找的话题的说法。你需要能够思考......并在算法层面向面试官解释你的想法......。这就是优秀候选人与普通候选人的区别。

Answer 2

有很多不同的方法可以解决这个问题，每一种都有自己的优点，所以我不会太担心你的答案是否是 'right' 那个......只要它实际解决问题！此外，面试官可能会对您的思维过程和您使用的策略更感兴趣，而不是在几分钟内在白板上写下 100% 完美的解决方案。

这里有两点需要考虑：

如您所见，您可以立即消除任何大于目标值的整数。
您实际上是在生成起始数组的任意大小的子集，因此 Set 可能是最有用的数据类型。当您生成响应集时，{2, 3} 和 {3, 2} 应该被视为相同。
整数划分是一个NP完全问题。这个很难（硬。我认为您采用了从数组而不是目标值开始的正确方法。
~~有许多算法可以从较大的集合中生成整数组合。查看此 SO answer 中的一些。您可以从您的（已过滤的）起始集合生成 k 大小的组合，对于 k 从 1-50。~~
实际上...有更直接的方法来获得起始集的 power set。考虑幂集的固有结构（如下所示）。通过列举几个示例，您会注意到识别子集的策略自然重复。

当您生成这些组合时，丢弃所有其元素总和不等于您的目标值的组合。

图片来源：https://en.wikipedia.org/wiki/Power_set

Answer 3

我知道生成你的随机数数组不是问题陈述的一部分，但我认为你的困难从这里开始。

首先，使用Set<Integer>类型的集合来收集你生成的号码；当集合达到所需大小时中断。如果生成的顺序很重要，请使用 LinkedHashSet。

Set<Integer> origSet = new HashSet<Integer>(); // fill with random numbers

有时，您有一个顺序很重要的数字列表。将此列表维护为 List<Integer>。该列表保留了原始列表的顺序，以便您可以按正确的顺序生成数字组合（即 6 在 1 之前，1 在 2 之前）。

List<Integer> origList = new ArrayList<Integer>(origSet); // use indexOf method to find index of a number

您创建了第二个已排序的列表；此列表是您的递归算法使用的列表。

List<Integer> sortedList = new ArrayList<Integer>(origList); // sort this

您不需要 trim 列表，因为递归算法会 trim 任何没有可行解的分支。

递归算法可以用更少的代码行生成组合。重新排序需要多几行。

Java 查找数组中所有加起来等于特定数字的组合

Java finding all combos in array that add up to specific number

java

algorithm

combinatorics