求遍历数组所有非空子集的统一实现方法（示例数组[1,2,3,4]）

给定数组 array = [1,2,3,4]，需要输出所有非空子集，预期输出如下：

1
2
3
4
1,2
1,3
1,4
2,3
2,4
3,4
1,2,3
1,2,4
1,3,4
2,3,4
1,2,3,4

两种无效尝试 #

仅输出二元子集的代码

for(int i = 0;i<n-1;i++){
   for(int j = i+1;j<n;j++){
       System.out.println(array[i]+","+array[j]);
   }
}

输出结果：

1,2
1,3
1,4
2,3
2,4
3,4

仅输出前缀子集的代码

for(int i = 0;i<n-1;i++){
   for(int j = 0;j<i+1;j++){
       System.out.print(array[j]);
   }
   System.out.println();
}

输出结果：

1
1,2
1,2,3
1,2,3,4

通用解法：二进制掩码法 #

对于包含n个元素的数组，每个子集可以用一个n位的二进制数表示——二进制数的每一位对应数组中的一个元素，若该位为1，则表示子集包含对应元素，为0则不包含。

以数组[1,2,3,4]为例，二进制数0001对应子集[1]，0011对应子集[1,2]，以此类推。我们只需要遍历从1到2^n - 1的所有整数（跳过0，因为对应空子集），对每个整数解析其二进制位，筛选出对应的元素即可。

Java实现代码如下：

public class SubsetGenerator {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4};
        int n = array.length;
        // 遍历所有非空子集：从1到2^n - 1
        for (int mask = 1; mask < (1 << n); mask++) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                // 检查第i位是否为1
                if ((mask & (1 << i)) != 0) {
                    if (sb.length() > 0) {
                        sb.append(",");
                    }
                    sb.append(array[i]);
                }
            }
            System.out.println(sb.toString());
        }
    }
}

运行这段代码后，将输出所有符合要求的非空子集，与预期格式完全一致。

内容的提问来源于stack exchange，提问作者Kavin V