我必须写一个有两个方法的代码,它需要一个数组(非负值)和一个值和作为参数。
public static void printSubsetSums(int[] arr, int sum) {
}
public static void printSubsetSums(int[] arr, int sum, int i, String acc)
{
}
我们不允许为当前方法添加方法或任何更多的参数.我做了一些类似的东西,只是根据一个给定的数组打印出子集的数量,但我很难改变它来完成这个任务...我的数组被限制在5的长度。
ecxample: "输入5个数字到数组 "输入:1 2 3 4 5 "输入一个数字到和 "输入:83。
为什么是3?(3,5) , (1,3,4) , (1,2,5)
谢谢你的帮助!!!
问题中提出的要求有点难以理解。然而,我已经编写了代码来满足你的用例。
我使用的方法如下。
用位操作法找出所有可能的数组子集
检查子集的总和是否等于给定的总和。如果是,则在控制台中打印出来。
请查看下面的代码段,以便更清楚地了解情况。
import java.util.Scanner;
public class SubsetSum {
public static void printSubsetSums(int[] arr, int sum) {
printSubsetSums(arr, sum, 0, "NotNeeded");
}
public static void printSubsetSums(int[] arr, int sum, int i, String acc) {
// variable 'i' and 'acc' are not getting used anywhere.
// Have added because you want to make the same syntax for the function.
boolean isAnySubsetPossible = false;
int n = arr.length;
// Run a loop from 0 to 2^n
for (int p = 0; p < (1 << n); p++) {
int[] temporaryArray = new int[n];
int k = 0;
int m = 1; // m is used to check set bit in binary representation.
// Print current subset
for (int j = 0; j < n; j++) {
if ((p & m) > 0) {
temporaryArray[k++] = arr[j];
}
m = m << 1;
}
int localSum = 0;
for (int temp : temporaryArray) {
localSum += temp;
}
if (localSum == sum) { // check if the sum is equal to the desired sum
isAnySubsetPossible = true;
for (int item : temporaryArray) {
if (item > 0) {
System.out.print(item + " ");
}
}
// print a new line so that next subset starts from new line
System.out.println();
}
}
if (!isAnySubsetPossible) {
System.out.println("There is no subset possible for the sum = " + 20);
}
}
public static void main(String[] args) {
Scanner myScanner = new Scanner(System.in);
System.out.println("Enter 5 numbers into array");
int[] myArr = new int[5];
for (int i = 0; i < myArr.length; i++) {
myArr[i] = myScanner.nextInt();
}
System.out.println("Enter a number into sum");
int sum = myScanner.nextInt();
printSubsetSums(myArr, sum);
}
}
程序的输入1
Enter 5 numbers into array
1 2 3 4 5
Enter a number into sum
8
程序的输出1
1 3 4
1 2 5
3 5
程序的输入2
Enter 5 numbers into array
1 2 3 4 5
Enter a number into sum
20
程序的输出2
There is no subset possible for the sum = 20
我希望这能帮助你。
我想你必须把一个数组作为输入,并给出一个整数的总和和能等于这个总和的整数。
在你的例子中。
输入5个数字到数组:1 2 3 4 5。
在和中输入一个数字:8 3 (这里我想3的意思是它只想让3个数字组成8,如 1 2 5 和 2 3 5 ...等)
你可以这样做 。
public static void printSubsetSums(int[] arr, int sum, int i) {
// getting all possible sub arrays of a lentgh of i
ArrayList<int[]> subarrays = new ArrayList<int[]>();
ArrayList<Integer> array = new ArrayList<Integer>();
int arrSize = arr.length;
for (int startPoint = 0; startPoint <arrSize ; startPoint++) {
for (int grps = startPoint; grps <=arrSize ; grps++) {
for (int j = startPoint ; j < grps ; j++) {
int element = arr[j];
array.add(element);
}
int[] tab = new int[array.size()];
int x = 0;
for(int n : array) {
tab[x] = n;
x++;
}
subarrays.add(tab);
array.clear();
}
}
// calculating the sum of each one of these arrays
// print the ones that their sum equal the sum given with argument
for(int[] al : subarrays) {
if (al.length==3) {
int sum2 = 0;
for (int n : al) {
sum2 = sum2 + n;
System.out.print(n);
}
System.out.print(" = "+sum2);
if(sum2==sum) { System.out.print(" that is a desired sum"); }
System.out.println();
}
}
}
下面是一个解决这个问题的递归方法。
public static void printSubsetSums(int[] arr, int sum) {
printSubsetSums(arr, sum, 0, "");
}
public static void printSubsetSums(int[] arr, int sum, int i, String acc)
{
if (sum == 0 && !"".equals(acc)) {
System.out.println(acc);
acc = "";
}
if (i == arr.length) {
return;
}
printSubsetSums(arr, sum, i + 1, acc);
printSubsetSums(arr, sum - arr[i], i + 1, acc+" "+arr[i]);
}
首先,你把你的整型数组和所需的总和输入到... printSubsetSums(int[] arr, int sum)
方法,该方法调用帮助者方法(printSubsetSums(int[] arr, int sum, int i, String acc)
),其中 i
是 arr
的指数和 acc
是如何得出总和的输出。
if (i == arr.length) { return; }
作为基本情况,退出递归方法 (i
是出界的)。)
请注意,我们有 两种 递归调用(printSubsetSums(arr, sum, i + 1, acc)
和 printSubsetSums(arr, sum - arr[i], i + 1, acc+" "+arr[i])
). 第一种行为是如果当前的数字将无法达到总和,从而使 i
中的下一个数字,递增为 "再试一次"。arr
. 第二种选择是,当前的数字可以使用,所以你继续下一个指数,同时考虑到当前的数字(将其从 sum
为了最终达到0[当我们知道所选的数字加起来确实是10时],将其加到 acc
).
最后,我们打印 acc
当 sum
为0,我们还设置 acc = ""
并避免打印时 "".equals(acc)
为了避免多次计算同一答案。
输入示例。
printSubsetSums(new int[]{1,2,3,4,5}, 8)
例子输出:
3 5
1 3 4
1 2 5