java - 使用数组并对元素求和

Question

我必须解决以下问题:给定一个整数数组并给定一个整数值，列出数组中所有可能的数字，总和为给定值。

示例:

Input: array = {1, 2, 2, 3, 4, 5}, int N = 5
Output: {1, 2, 2}, {1, 4}, {5} {2, 3}.

到目前为止，这是我的代码，有人可以帮助我吗？

import java.util.Scanner;

public class sumarray {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        int[] array = new int[3];
        for (int i = 0; i < array.length; i++) {
            array[i] = scan.nextInt();

        }

        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length; j++) {
                if (array[i] + array[j] == 5) {
                    System.out.println("{" + array[i] + "," + array[j] + "}");
                }
            }
        }
    }
}

Answer 1

这是一个常见的Dynamic Programming问题名为 Subset Sum .

如果您只想打印，您可以这样做(请注意，您有 {2, 3} 两次，因为有两个 2):

public class Main {

    public static void main(String[] args){
        int[] arr = {1, 2, 2, 3, 4, 5};
        subsetSum(arr, 5);
    }

    private static void subsetSum(int[] arr, int sum) {
        subsetSum(arr, 0, sum, "");
    }

    private static String lineSep = System.getProperty("line.separator");
    private static void subsetSum(int[] arr, int i, int sum, String aggregated) {
        if (sum == 0){
            System.out.println("Success with:" + aggregated);
            System.out.println("And done.");
            System.out.println();
            return;
        }
        if (arr.length <= i){
//             failed (uncomment following lines to see why)
//             System.out.println("Failed with:" + aggregated);
//             System.out.println();
            return;
        }

        int current = arr[i];

        subsetSum(arr, i+1, sum, aggregated + lineSep + "not " + current);
        subsetSum(arr, i+1, sum - current, aggregated + lineSep + current);
        return;
    }
}

这利用了String不可变的事实(因此为每个帧创建一个新字符串)，并对选定的数字进行前向聚合。我添加了一些文字以使其具有描述性，以便您了解发生了什么。

输出:

not 1
not 2
not 2
not 3
not 4
5
And done.

not 1
not 2
2
3
And done.

not 1
2
not 2
3
And done.

1
not 2
not 2
not 3
4
And done.

1
2
2
And done.