【每日算法】LeetCode 78. 子集

对前端开发者而言，学习算法绝非为了"炫技"。它是你从"页面构建者"迈向"复杂系统设计者"的关键阶梯。它将你的编码能力从"实现功能"提升到"设计优雅、高效解决方案"的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 78. 子集

1. 题目描述

给定一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例：

输入:nums=[1,2,3]输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

前端场景联想：

• 权限系统的所有权限组合
• 商品筛选器的所有筛选条件组合
• 表单中可选的字段组合
• 可视化图表中可显示的数据维度组合

2. 问题分析

2.1 问题本质

子集问题本质上是组合问题，需要找出给定集合的所有可能组合。对于长度为 n 的数组，总共有 2^n 个子集（包括空集）。

2.2 关键特性

1. 元素唯一性：题目明确数组元素互不相同，无需去重
2. 幂集性质：结果集合大小为 2^n
3. 顺序无关：子集内元素顺序不重要，但通常按原数组顺序

2.3 前端视角分析

在前端开发中，这种问题常见于：

• 动态表单字段组合
• 可配置组件的参数组合
• 路由权限的组合验证
• 数据可视化中的维度组合

3. 解题思路

3.1 思路概览

最优解：三种方法时间复杂度相同，但回溯法在可读性和灵活性上更优，尤其适合前端开发者理解和实现。

3.2 详细思路分析

3.2.1 回溯法（深度优先搜索）

核心思想：每个元素有"选"或"不选"两种选择，构建决策树。

3.2.2 迭代法（广度优先搜索）

核心思想：从空集开始，每次添加新元素到已有子集中。

3.2.3 位运算法

核心思想：用二进制位表示元素的选择状态（1选，0不选）。

4. 各思路代码实现

4.1 回溯法实现

/** * 回溯法 - 最符合前端思维的模式 * @param {number[]} nums * @return {number[][]} */constsubsets=function(nums){constresult=[];/** * 回溯函数 * @param {number} index - 当前处理的元素索引 * @param {number[]} current - 当前子集 */constbacktrack=(index,current)=>{// 所有元素都已处理，保存当前子集if(index===nums.length){result.push([...current]);// 深拷贝return;}// 选择1：不包含当前元素backtrack(index+1,current);// 选择2：包含当前元素current.push(nums[index]);backtrack(index+1,current);current.pop();// 回溯，撤销选择};backtrack(0,[]);returnresult;};// 变体：更直观的循环回溯（前端更常用）constsubsetsWithLoop=function(nums){constresult=[];constdfs=(start,path)=>{// 每次递归都保存当前路径（子集）result.push([...path]);// 从start开始遍历，避免重复for(leti=start;i<nums.length;i++){path.push(nums[i]);// 做出选择dfs(i+1,path);// 递归path.pop();// 撤销选择}};dfs(0,[]);returnresult;};

4.2 迭代法实现

/** * 迭代法 - 类似动态扩展 * @param {number[]} nums * @return {number[][]} */constsubsetsIterative=function(nums){// 从空集开始letresult=[[]];for(letnumofnums){// 获取当前所有子集的数量constcurrentLength=result.length;// 为每个现有子集添加当前元素for(leti=0;i<currentLength;i++){constnewSubset=[...result[i],num];result.push(newSubset);}}returnresult;};// 更简洁的迭代写法（ES6+）constsubsetsIterativeES6=(nums)=>{returnnums.reduce((subsets,num)=>subsets.concat(subsets.map(subset=>[...subset,num])),[[]]);};

4.3 位运算实现

/** * 位运算法 - 利用二进制掩码 * @param {number[]} nums * @return {number[][]} */constsubsetsBitwise=function(nums){constn=nums.length;consttotal=1<<n;// 2^nconstresult=[];// 遍历所有可能的掩码（0 到 2^n-1）for(letmask=0;mask<total;mask++){constsubset=[];// 检查每个位是否被设置for(leti=0;i<n;i++){// 如果第i位是1，则包含nums[i]if(mask&(1<<i)){subset.push(nums[i]);}}result.push(subset);}returnresult;};

5. 各实现思路对比

5.1 优缺点详细分析

回溯法

优点：

1. 代码结构清晰，符合递归思维
2. 容易理解和调试
3. 易于修改以适应变化需求（如限制子集大小）
4. 在前端树形结构操作中常见，思维模式可迁移

缺点：

1. 递归可能导致栈溢出（但此题深度n≤10，安全）
2. 需要理解递归和回溯的概念

迭代法

优点：

1. 无递归栈开销
2. 代码相对简洁
3. 适合理解动态构建过程

缺点：

1. 不如回溯法直观
2. 当需要条件限制时修改较复杂

位运算法

优点：

1. 性能最优
2. 数学上最优雅
3. 内存使用最少

缺点：

1. 可读性差，难以维护
2. 需要理解位运算
3. 当n较大时（>32）JavaScript有数字精度问题

6. 总结

6.1 核心要点回顾

1. 子集问题本质是组合问题，结果数量为 2^n
2. 回溯法是最平衡的解决方案，特别适合前端开发者
3. 递归思维在前端开发中极其重要（组件树、DOM树、状态树）
4. 算法思想比具体实现更重要

6.2 实际前端应用场景

场景1：权限系统

// 用户权限子集检查constuserPermissions=['read','write','delete','admin'];constrequiredPermissions=['read','write'];// 检查用户权限是否包含所需权限的所有子集组合functioncheckPermission(userPerms,requiredPerms){constuserPermSet=newSet(userPerms);returnrequiredPerms.every(perm=>userPermSet.has(perm));}

场景2：商品筛选器

// 电商平台的多条件筛选constfilters=['price','category','brand','rating'];// 生成所有可能的筛选组合functiongenerateFilterCombinations(filters){constresult=[];constdfs=(index,current)=>{result.push([...current]);for(leti=index;i<filters.length;i++){current.push(filters[i]);dfs(i+1,current);current.pop();}};dfs(0,[]);returnresult;}

场景3：动态表单配置

// 根据用户角色显示不同的表单字段组合constallFormFields=['name','email','phone','address','payment'];constroleFieldSubsets={guest:['name','email'],user:['name','email','address'],admin:['name','email','phone','address','payment']};// 生成可配置的表单字段组合functiongetAvailableFields(role){returnroleFieldSubsets[role]||[];}