手机网站模板制作,建筑教育,上海社保,综合办公oa系统Problem: 78. 子集 文章目录 题目描述思路及解法复杂度Code 题目描述 思路及解法 1.定义一维数组track用于记录决策路径#xff0c;二维数组res用于存储所有的子集#xff1b; 2.决策阶段#xff1a;从0阶段起来#xff08;0阶段决策路径中为空集#xff09;#xff0c;每… Problem: 78. 子集 文章目录 题目描述思路及解法复杂度Code 题目描述 思路及解法 1.定义一维数组track用于记录决策路径二维数组res用于存储所有的子集 2.决策阶段从0阶段起来0阶段决策路径中为空集每次将当前阶段的决策路径添加到res中为了保证元素的不重复我们要保证原始数组nums中元素的相对顺序则在利用回溯模板解题时我们每次使得循环中的索引起始位置从当前的决策阶段开始 复杂度
时间复杂度: O ( N × 2 N ) O(N \times 2^N) O(N×2N);其中 N N N为数组nums的长度 空间复杂度: O ( N ) O(N) O(N) Code
class Solution {//Recode the resultvectorvectorint res;//Recode the Decision pathvectorint track;
public:/*** subset* * param nums Universe* return vectorvectorint*/vectorvectorint subsets(vectorint nums) {backtrack(nums, 0);return res;}/*** Backtracking function* * param nums Universe* param start Decision stage*/void backtrack(vectorint nums, int start) {res.push_back(track);for (int i start; i nums.size(); i) {track.push_back(nums[i]);backtrack(nums, i 1);track.pop_back();}}
};
