网站设计O2O平台优化,国际进出口贸易网站,wordpress oss压缩,在线图片编辑器官网题目链接#xff1a;78. 子集
题目描述
给你一个整数数组 nums #xff0c;数组中的元素 互不相同 。返回该数组所有可能的子集#xff08;幂集#xff09;。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1#xff1a;
输入#xff1a;nums [1,2…题目链接78. 子集
题目描述
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1
输入nums [1,2,3]
输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2
输入nums [0]
输出[[],[0]]提示
1 nums.length 10-10 nums[i] 10nums 中的所有元素 互不相同
文章讲解代码随想录
视频讲解回溯算法解决子集问题树上节点都是目标集和 | LeetCode78.子集_哔哩哔哩_bilibili
题解1回溯法
思路使用回溯法来求解子集类问题。
回溯分析
递归函数的参数和返回值首先创建2个变量 res 和 pathpath 记录遍历的路径res 记录结果。递归函数的返回值为 void参数是 start用来记录本次递归的开始位置。递归函数的终止条件找到叶子节点即 start 和 nums.length 相同也就是查找完毕。单层递归的逻辑将当前路径作为子集记录到结果数组中使用 for 循环从开始位置 start 开始直到 nums.length 横向遍历递归的向下纵向遍历寻找组合。剪枝无。
/*** param {number[]} nums* return {number[][]}*/
var subsets function(nums) {const res []; // 结果数组const path []; // 路径const backtracking function (start) {res.push([...path]); // 将节点的值记录进结果数组for (let i start; i nums.length; i) {path.push(nums[i]); // 记录路径backtracking(i 1); // 向下查找path.pop(); // 回溯}}backtracking(0);return res;
};
分析时间复杂度为 O(n * 2 ^ n)空间复杂度为 O(n)。
收获
学习了使用回溯法求解子集问题收集结果在所有节点上都需要进行。
