<分区>
我目前正在研究面试书中的以下问题:
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,您将返回 [[3,6],[6,1,2 ],[9],[3,1,5]]。在数组中返回结果的顺序无关紧要,尽管您应该返回唯一的集合(即 [6,3] 和 [3,6] 相同,并且只应返回一个)。此外,各个结果应按照找到它们的顺序排列(即应返回 [6,1,2],而不是 [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));
}
}
}
我知道这是不完整的,但我想问问是否有人对此有任何建议或改进?我整理了我的列表并删除了所有可能不会被使用的整数,但现在困难的部分是找到所有的组合。