美妆网站建设方案,青岛网站建设收费哪个平台好,jsp网站开发技术,装饰公司广告语题#xff1a;给你一个整数数组 nums #xff0c;数组中的元素 互不相同 。返回该数组所有可能的子集#xff08;幂集#xff09;。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
方法一#xff1a;迭代法 核心逻辑#xff1a;动态扩展子集#xff0c; 小规…题给你一个整数数组 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)
场景选择建议 竞速场景优先选择迭代法代码最简 复杂变体使用回溯法方便添加剪枝条件如子集大小限制 理论研究递归法便于数学证明
