题目地址
https://leetcode.com/problems/subsets/description/
题目描述
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
思路
这道题目是求集合,并不是求极值
,因此动态规划不是特别切合,因此我们需要考虑别的方法。
这种题目其实有一个通用的解法,就是回溯法。
网上也有大神给出了这种回溯法解题的
通用写法,这里的所有的解法使用通用方法解答。
除了这道题目还有很多其他题目可以用这种通用解法,具体的题目见后方相关题目部分。
我们先来看下通用解法的解题思路,我画了一张图:
通用写法的具体代码见下方代码区。
关键点解析
- 回溯法
- backtrack 解题公式
代码
- 语言支持:JS,C++
JavaScript Code:
/* * @lc app=leetcode id=78 lang=javascript * * [78] Subsets * * https://leetcode.com/problems/subsets/description/ * * algorithms * Medium (51.19%) * Total Accepted: 351.6K * Total Submissions: 674.8K * Testcase Example: '[1,2,3]' * * Given a set of distinct integers, nums, return all possible subsets (the * power set). * * Note: The solution set must not contain duplicate subsets. * * Example: * * * Input: nums = [1,2,3] * Output: * [ * [3], * [1], * [2], * [1,2,3], * [1,3], * [2,3], * [1,2], * [] * ] * */ function backtrack(list, tempList, nums, start) { list.push([...tempList]); for(let i = start; i < nums.length; i++) { tempList.push(nums[i]); backtrack(list, tempList, nums, i + 1); tempList.pop(); } } /** * @param {number[]} nums * @return {number[][]} */ var subsets = function(nums) { const list = []; backtrack(list, [], nums, 0); return list; };
C++ Code:
class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { auto ret = vector<vector<int>>(); auto tmp = vector<int>(); backtrack(ret, tmp, nums, 0); return ret; } void backtrack(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(); } } };
相关题目
- 39.combination-sum
- 40.combination-sum-ii
- 46.permutations
- 47.permutations-ii
- 90.subsets-ii
- 113.path-sum-ii
- 131.palindrome-partitioning
爱丽丝和鲍勃一起玩游戏,他们轮流行动。爱丽丝先手开局。最初,黑板上有一个数字 N 。在每个玩家的回合,玩家需要执行以下操作:选出任一 x,满足 0 < x < N 且 N % x == 0 。用 N - x 替换黑板上的数字 N 。如果玩家无法执行这些操作,就会输掉游戏。只有在爱丽丝在游戏中取得胜利时才返回 True,否则返回 false。假设两…
Java中的“ <<”运算符 - java最喜欢的语句来自Java的Character类:(1 << Character.PARAGRAPH_SEPARATOR)) >> type PARAGRAPH_SEPARATOR是字节,type是整数。这句话中的操作员,他们做什么?如何以及在哪里可以使用这些运算符?这是oracles java.lang.Character文档。该类中…
LeetCode题解计算机为什么是基于二进制的?可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制
LeetCode题解统计城市的所有灯泡这个是我刚毕业的时候,一个真实的面试题,这是一个开放题。题目描述:想办法,将一个城市的所有灯泡数量统计出来。题解:费米估算法1、如果某个城市常驻人口有1000万2、假设每5人居住在一套房里,每套房有灯泡5只,那么住宅灯泡共有1000万只3、假设公众场所每10人共享一只灯泡,那么共有100万只4、主要的这两者相加就得出了1100万只当然实际上这是估算的,具体应…
LeetCode题解黑白圆盘一个圆盘被涂上了黑白二色,两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?题解:可以用一个相机即可