java - 使用数组中的第一个 'n' 整数递归打印所有子集

Question

使用数组的前 n 个整数递归地打印可能的子集。示例:int[] X = [1, 2, 3, 4]，如果 n = 3，则打印 [3, 2, 23, 1, 13, 12, 123]

我已经坐在这里几个小时了，我盲目地尝试过，现在向你们寻求帮助!这是我到目前为止所拥有的。它离答案还很远，所以请耐心等待。

static void subsets(int[] A, int n){
    subsets("", A, n);
}
private static void subsets(String S, int[] A, int n){
    if(n == 0){
        System.out.println(S);
    } else {
        for (int i = n-1; i >= 0; i--) {
            subsets(A[n-i-1]+S, A, n-i);
        }
    }
}

Answer 1

解决这个子集问题的方法有很多，但我特别喜欢下面的方法。

它依赖于这样一个事实:当您以二进制形式从 1 数到 N(N 是 2 的幂)时，这些位会包含所有可能的唯一组合。因此，如果您将每个位“附加”到数组中的特定值，您将获得值的所有可能组合。

在您的示例中，您在数组中采用 N = 3 个值。用N位，可以得到2^3 (或 1<<3 )= 8 个不同的值。因此，让我们用二进制数从 0 到 7，并观察每一步打开或关闭的位:

• 1 = 001 -> 仅获取列表中的第一项
• 2 = 010 -> 仅选取列表中的第二项
• 3 = 011 -> ...
• 4 = 100
• 5 = 101 -> 获取列表中的第一个和第三个元素
• 6 = 110
• 7 = 111

现在你已经找到了 N 个元素中所有可能的子集。

这是代码:

int[] nums = new int[]{1, 2, 3, 4};
int n = 3;

int maxValueOnNBits = 1 << n;

for (int i = 1; i <= maxValueOnNBits; i++) {
    for (int bit = 0; bit < n; bit++) {
        int mask = 1 << bit;
        if ((i & mask) == mask) System.out.print(nums[bit]);
    }
    System.out.println();
}