递归地打印数组中等于给定总和的所有子集

Question

我必须用两种方法编写代码，这两种方法采用数组（非负）和值总和作为参数。我必须使用以下方法：

public static void printSubsetSums(int[] arr, int sum) {

}

public static void printSubsetSums(int[] arr, int sum, int i, String acc) 
{

}

我们不允许为当前方法添加方法或任何更多参数。我做了类似的事情，只是根据总和打印给定数组中的子集数。但我很难改变它来完成这项任务...... 我的数组长度限制为 5.

示例： "Enter 5 numbers to array" input:1 2 3 4 5 "Enter a number into sum" input:8 3

为什么是 3 个？ (3,5) , (1,3,4) , (1,2,5)

感谢您的帮助！！！

Answer 1

我认为你必须将一个数字数组作为输入，并给出可以等于这个和的整数的总和和个数

在你的例子中：

输入 5 个数字到数组：1 2 3 4 5

Enter a number into sum : 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();
        }
    }

}

Answer 2

问题中的要求有点难以理解。但是，我已经编码来满足您的用例。

我使用的方法如下：

使用位操作方法找到给定数组的所有可能子集。
检查子集的总和是否等于给定的总和。如果是，则在控制台打印。

查看下面的代码片段更清楚。

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

Input1 到程序

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

Input2 到程序

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

希望对您有所帮助。

Answer 3

这是解决这个问题的递归方法：

    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, int i, String acc)) 的 printSubsetSums(int[] arr, int sum) 方法中，其中 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 递增到 "try again"，下一个数字在 arr 中。第二个选项是当前数字将起作用，因此您在考虑当前数字的同时继续下一个索引（从 sum 中减去它以最终达到 0 [当我们知道所选数字确实加起来 10] 并将其添加到 acc).

最后，当sum为0时，我们打印acc。我们还设置acc = ""，避免在"".equals(acc)时打印，以避免相同的答案被统计多次次。

结果：

示例输入：

printSubsetSums(new int[]{1,2,3,4,5}, 8)

示例输出：

 3 5
 1 3 4
 1 2 5

Answer 4

给定所有子集的总和，建议一种算法或方法来打印数组的 elements/integers。

例如，给定子集的总和； {0,1,2,3} --> 数组的值是，arr[] = {1,2}，其子集是 {{} -> sum is '0', {1} -> sum是 '1', {2} -> 和是 2, {1,2} -> 和是 '3'}; 注意：给定数组中的所有值都是正数 N>=0;

递归地打印数组中等于给定总和的所有子集

Print all subsets in an array that equal to a given sum recursively

java

arrays

recursion

subset

subset-sum

解释：

结果：