java - 递归以获取数组中的所有变体总和

Question

我正在尝试编写一个递归方法，允许我对数组中所有可能的整数变体求和。

例如。对于具有以下值的数组 [1, 2, 3, 4]

结果:[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3], [1, 2, 3], [1, 2, 4], [2, 1, 3] , [2, 1, 4] 等等等等。

我对递归完全陌生。我的理解是把问题分成一个更小的问题。但我似乎看不到这种情况。有人可以帮我吗？

编辑:

class Stick {

    public int sum(ArrayList<Integer> array) { 
        int total = 0;
        for(int i = 0; i < array.size(); i++) {
            total += array.get(i);
        }

        return total;
    }

    public void permute(ArrayList<Integer> in, ArrayList<Integer> out) {
        if(out.size() > 0) { print(out); System.out.println(sum(out)); }

        for(int i = 0; i < in.size(); i++) { 
            int item = in.get(i);
            in.remove(i);
            out.add(item);
            permute(in , out);
        }
    }

    public void print(ArrayList<Integer> integer) {
        System.out.print("[");
        for(int i = 0; i < integer.size(); i++) {
            System.out.print(integer.get(i) + ", ");
        }
        System.out.print("]");
    }
    public static void main(String[] args) {
        ArrayList<Integer> in = new ArrayList<Integer>();
        ArrayList<Integer> out = new ArrayList<Integer>();
        in.add(1); in.add(2); in.add(3); in.add(4);

        Stick stick = new Stick();
        stick.permute(in, out);
    }
}

Answer 1

static ArrayList<int[]> permutations(int[] a) {
    ArrayList<int[]> ret = new ArrayList<int[]>();
    permutation(a, 0, ret);
    return ret;
}

public static void permutation(int[] arr, int pos, ArrayList<int[]> list) {
    if (arr.length - pos == 1) {
        list.add(arr.clone());
    } else {
        for (int i = pos; i < arr.length; i++) {
            swap(arr, pos, i);
            permutation(arr, pos + 1, list);
            swap(arr, pos, i);
        }
    }
}

public static void swap(int[] arr, int pos1, int pos2) {
    int h = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = h;
}

public static void main(String[] args) {
    int[] x = {1, 2, 3, 4};
    for(int i[] : IntRecursion.permutations(x)) {
        System.out.println(Arrays.toString(i));
    }

}

我想这就是您要找的。