Skip to content

Latest commit

 

History

History
163 lines (130 loc) · 3.69 KB

78.subsets.md

File metadata and controls

163 lines (130 loc) · 3.69 KB

题目地址(78. 子集)

https://leetcode-cn.com/problems/subsets/

题目描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ]

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

回溯的基本思路清参考上方的回溯专题。

子集类题目和全排列题目不一样的点在于其需要在递归树的所有节点执行加入结果集 这一操作，而不像全排列需要在叶子节点执行加入结果集。

关键点解析

  • 回溯法
  • backtrack 解题公式

代码

  • 语言支持：JS，C++，Java，Python

JavaScript Code:

functionbacktrack(list,tempList,nums,start){list.push([...tempList]);for(leti=start;i<nums.length;i++){tempList.push(nums[i]);backtrack(list,tempList,nums,i+1);tempList.pop();}}/** * @param {number[]} nums * @return {number[][]} */varsubsets=function(nums){constlist=[];backtrack(list,[],nums,0);returnlist;};

C++ Code：

classSolution { public: vector<vector<int>> subsets(vector<int>& nums) { auto ret = vector<vector<int>>(); auto tmp = vector<int>(); backtrack(ret, tmp, nums, 0); return ret; } voidbacktrack(vector<vector<int>>& list, vector<int>& tempList, vector<int>& nums, int start) { list.push_back(tempList); for (auto i = start; i < nums.size(); ++i) { tempList.push_back(nums[i]); backtrack(list, tempList, nums, i + 1); tempList.pop_back(); } } };

Java Code：

classSolution { // 结果List<List<Integer>> res = newArrayList(); publicList<List<Integer>> subsets(int[] nums) { backtrack(nums, 0, newArrayList<Integer>()); returnres; } publicvoidbacktrack(int[] nums, intstart, ArrayList<Integer> track) { // 注意：深拷贝res.add(newArrayList(track)); for(inti=start; i<nums.length;i++) { // 做选择track.add(nums[i]); // 回溯backtrack(nums, i+1, track); // 撤销选择track.remove(track.size()-1); } } }

python Code：

classSolution: defsubsets(self, nums): self.res= [] self.track= [] self.backtrack(nums, 0, self.track) returnself.resdefbacktrack(self, nums, start, track): # 注意深拷贝self.res.append(list(self.track)) foriinrange(start, len(nums)): # 做选择self.track.append(nums[i]) # 回溯self.backtrack(nums, i+1, self.track) # 撤销选择self.track.pop()

相关题目

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

close