算法-js-子集

题：给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

方法一：迭代法
核心逻辑：动态扩展子集， 小规模数据（n ≤ 20）推荐

const subsets = (nums) => {const result = [[]];for (const num of nums) {const n = result.length;for (let i = 0; i < n; i++) {result.push([...result[i], num]);}}return result;
};

方法二：回溯法（DFS+剪枝）
核心逻辑：通过深度优先搜索遍历所有决策路径

const subsets = (nums) => {const result = [];const backtrack = (start, path) => {result.push([...path]); // 记录当前路径for (let i = start; i < nums.length; i++) {path.push(nums[i]);    // 选择当前元素backtrack(i + 1, path); // 递归下一层path.pop();           // 撤销选择（回溯）}};backtrack(0, []);return result;
};

方法三：递归分治法
核心逻辑：基于数学归纳法递推生成子集

const subsets = (nums) => {if (nums.length === 0) return [[]];const last = nums.pop();const prevSubsets = subsets(nums); // 递归获取前n-1元素的子集const newSubsets = prevSubsets.map(sub => [...sub, last]); return [...prevSubsets, ...newSubsets]; // 合并新旧子集
};

时间复杂度均为O(n*2^n)

场景选择建议
竞速场景：优先选择迭代法（代码最简）
复杂变体：使用回溯法（方便添加剪枝条件，如子集大小限制）
理论研究：递归法（便于数学证明）