本文详解如何利用二进制位掩码（bitmask）在java中高效生成并输出集合s的所有r元子集，涵盖用户输入处理、掩码遍历、子集筛选与计数，并提供可直接运行的完整代码。
本文详解如何利用二进制位掩码（bitmask）在java中高效生成并输出集合s的所有r元子集，涵盖用户输入处理、掩码遍历、子集筛选与计数，并提供可直接运行的完整代码。
在组合数学与算法实践中，枚举集合的所有 r-子集（即恰好含 r 个元素的子集）是一个经典问题。题目要求使用“掩码”（mask）方法实现——这并非额外数据结构，而是巧妙利用整数的二进制表示：对一个大小为 n 的集合 S，可用一个 n 位二进制数（即 0 到 2ⁿ−1 之间的整数）作为掩码，其中第 i 位为 1 表示 S[i] 被选入当前子集，为 0 则未被选中。例如，集合 S = [1,2,3] 对应掩码 101₂ = 5 时，表示子集 {1,3}。
该方法时间复杂度为 O(2ⁿ × n)，适用于题目约束（|S| ≤ 10），且逻辑清晰、位运算高效（&,
以下是完整可运行的 Java 实现：
java-api-doc-generator
下载
分析 Java Spring Boot 后端 Controller 代码，自动生成 Markdown 格式的接口文档。当用户说“生成 Java 接口文档”、“生成 API 文档”、“从 Spring 代码生成文档”时触发。
import java.util.*;
public class SubsetGenerator {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
// 步骤1：读取用户输入
System.out.print("Please enter S: ");
String[] sValues = input.nextLine().trim().split("\s+");
int n = sValues.length;
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(sValues[i]);
}
System.out.print("Please enter r: ");
int r = input.nextInt();
// 存储所有满足条件的子集（便于格式化输出）
List<List<Integer>> rSubsets = new ArrayList<>();
// 步骤2 & 3：遍历所有掩码（0 到 2^n - 1），筛选出大小为 r 的子集
int totalMasks = 1 << n; // 即 2^n
for (int mask = 0; mask < totalMasks; mask++) {
List<Integer> subset = new ArrayList<>();
// 检查掩码中每一位，提取对应元素
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) { // 第i位为1？
subset.add(arr[i]);
}
}
// 仅当子集大小等于r时保留
if (subset.size() == r) {
rSubsets.add(subset);
}
}
// 步骤4：按题目格式输出
System.out.println(r + "-subsets of S are the following:");
for (List<Integer> subset : rSubsets) {
System.out.print("{ ");
for (int i = 0; i < subset.size(); i++) {
System.out.print(subset.get(i));
if (i < subset.size() - 1) System.out.print(" ");
}
System.out.println(" }");
}
System.out.println("There are " + rSubsets.size() + " r-subsets");
}
}关键说明与注意事项：
立即学习“Java免费学习笔记（深入）”；
- 掩码范围：for (int mask = 0; mask
- 位检测逻辑：(mask & (1
- 索引对齐：掩码第 0 位对应 arr[0]（即输入的第一个元素），确保顺序一致；输出子集时元素顺序与输入顺序相同，符合题目“顺序无关但输出按输入顺序”的隐含要求。
- 健壮性：代码自动处理空格分隔的输入（支持多空格/首尾空格），无需预先输入集合大小，更贴合示例交互风格。
- 性能提示：当 n=10 时，最多遍历 1024 个掩码，完全满足要求；若后续需扩展至更大规模，应改用递归回溯或迭代组合生成器以避免指数级开销。
通过本方案，你不仅完成了作业要求，更掌握了位掩码这一在算法竞赛与底层编程中广泛应用的核心技巧——它将集合操作映射为简洁、高速的整数位运算，是空间与效率兼顾的经典范式。
