java - 递归 - 与 in array 组合，在 Java 中没有重复

Question

所以我知道如何获得组合的大小 - 数组大小(在我的例子中)与所需数组子集大小的阶乘。我遇到的问题是获取组合。到目前为止，我已经在 stackoverflow 上阅读了大部分问题，但一无所获。我认为我发现的问题是我想将创建的组合子集中的元素加在一起。总之，这应该递归地完成

所以澄清一下:

int[] array = {1,2,3,4,5};

子集的大小为 2，组合为

{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}

根据这些数据，我想看看子集是否说...等于 6，那么答案将是: {1,5} 和 {2,4} 给我留下一组 {1,5,2,4}

到目前为止我有这个:

 public static int[] subset(int[] array, int n, int sum){
     // n = size of subsets
     // sum = what the sum of the ints in the subsets should be 

    int count = 0; // used to count values in array later
    int[] temp = new temp[array.length]; // will be array returned

    if(array.length < n){
        return false;
    }

    for (int i = 1; i < array.length; i++) {
        for (int j = 0; j < n; j++) {
            int[] subset = new int[n];
            System.arraycopy(array, 1, temp, 0, array.length - 1); // should be array moved forward to get new combinations

                           **// unable to figure how how to compute subsets of the size using recursion so far have something along these lines**
                            subset[i] = array[i];
                            subset[i+1] = array[i+1];

                            for (int k = 0; k < n; k++ ) {
                               count += subset[k];
                            }
                           **end of what I had **

            if (j == n && count == sum) {
                temp[i] = array[i];
                                    temp[i+1] = array[i+1];
            }
        }
    } subset(temp, n, goal);

    return temp;
}

我应该如何计算可用子集的可能组合？

Answer 1

我希望你会爱我。您唯一需要做的就是将结果合并到一个数组中，但它会检查所有可能性(尝试运行程序并查看输出):) :

public static void main(String[] args) {
    int[] array = {1, 2, 3, 4, 5};
    int n = 2;
    subset(array, n, 6, 0, new int[n], 0);
}

public static int[] subset(int[] array, int n, int sum, int count, int[] subarray, int pos) {
    subarray[count] = array[pos];
    count++;

    //If I have enough numbers in my subarray, I can check, if it is equal to my sum
    if (count == n) {
        //If it is equal, I found subarray I was looking for
        if (addArrayInt(subarray) == sum) {
            return subarray;
        } else {
            return null;
        }
    }

    for (int i = pos + 1; i < array.length; i++) {
        int[] res = subset(array, n, sum, count, subarray.clone(), i);
        if (res != null) {
            //Good result returned, so I print it, here you should merge it
            System.out.println(Arrays.toString(res));
        }
    }

    if ((count == 1) && (pos < array.length - 1)) {
        subset(array, n, sum, 0, new int[n], pos + 1);
    }

    //Here you should return your merged result, if you find any or null, if you do not
    return null;
}

public static int addArrayInt(int[] array) {
    int res = 0;
    for (int i = 0; i < array.length; i++) {
        res += array[i];
    }
    return res;
}