标题翻译
count of subset with given sum
问题
我试图找到一种方法来返回与总和相等的子集的计数。数组包含5个数字。我写了一段代码，最后统计了所有分支的数量，而不是正确的与总和相等的子集，我无法找出如何更改它。
import java.util.*;
public class Assignment4 {
public static int countSubsetSums(int[] arr, int sum) {
return countSubsetSums(arr, sum, 0);
}
public static int countSubsetSums(int[] arr, int sum, int i) {
int count = 0;
if (sum == 0) {
count++;
} else if (i >= arr.length) {
return count;
} else {
if (sum >= 0) {
count = countSubsetSums(arr, sum - arr[i], i++) + countSubsetSums(arr, sum, i++);
}
}
return count;
}
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();
System.out.println(countSubsetSums(myArr, sum));
}
}
注意： 请确保在使用此代码之前进行测试和验证，以确保其按预期工作。
英文翻译
I was trying to find a way to give back the count of subsets that are equal to the sum. the array would include 5 numbers. I wrote a code that at the end counts all the branches instead of the correct subsets that are equal to the sum and I can't find out how to change it.
import java.util.*;
public class Assignment4 {
public static int countSubsetSums(int[] arr, int sum) {
return countSubsetSums(arr,sum, 0);
}
public static int countSubsetSums(int[] arr, int sum, int i) {
int count=0;
if(sum==0) {
count++;
}
else if(i >= arr.length) {
return count;
}
else {
if(sum>=0) {
count= countSubsetSums(arr, sum- arr[i], i++) + countSubsetSums(arr, sum, i++);
}
}
return count;
}
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();
System.out.println(countSubsetSums(myArr,sum));
}
}
答案1
得分: 0
我认为你的逻辑大部分是正确的，但是基本情况有些出错（下面是修正后的代码）：
如果 i 超出了边界或者 sum 为负数，则不存在子集的和等于给定的 sum，从 i 开始往后，所以我们返回 0。
如果 sum 等于 0，则 arr 只有一个子集的和等于 sum，即空子集（假设 arr 的元素严格为正数。如果 arr 可以包含 0，则这就是一个完全不同的问题）。
最后，如果 a[i] 小于 sum，则我们可以添加使用 a[i] 的子集的计数，否则我们只计算不使用 a[i] 的子集的数量。
public static int countSubsetSums(int[] arr, int sum) {
return countSubsetSums(arr, sum, 0);
}
public static int countSubsetSums(int[] arr, int sum, int i) {
if (i >= arr.length || sum < 0) {
return 0;
}
if (sum == 0) {
return 1;
}
int count = 0;
if (arr[i] <= sum) {
count = countSubsetSums(arr, sum - arr[i], i + 1);
}
count += countSubsetSums(arr, sum, i + 1);
return count;
}
英文翻译
I think your logic was mostly right, but the base cases were a little off (fixed code below):
If i is out of bounds or sum is negative, then there is no subsets that sum to the given sum starting past i, so we return 0.
If the sum is equal to 0, then there is only one subset of arr that equals sum which is the empty subset (assuming arr elements are strictly positive. If arr can include 0s, then this is a totally different problem).
Lastly, if a[i] is less than sum, then we can add the count of subsets that use a[i] else we just counts subsets without a[i]
public static int countSubsetSums(int[] arr, int sum) {
return countSubsetSums(arr,sum, 0);
}
public static int countSubsetSums(int[] arr, int sum, int i) {
if (i >= arr.length || sum < 0) {
return 0;
}
if (sum == 0) {
return 1;
}
int count=0;
if (arr[i] <= sum) {
count = countSubsetSums(arr, sum - arr[i], i+1);
}
count += countSubsetSums(arr, sum, i+1);
return count;
}
专注分享java语言的经验与见解，让所有开发者获益！
评论