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], []]
Solution: Combination
Time complexity: O(2^n)
Space complexity: O(n)
Implemention 1: DFS
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua, running time: 4 ms class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> ans; vector<int> cur; for (int i = 0; i <= nums.size(); ++i) dfs(nums, i, 0, cur, ans); return ans; } private: void dfs(const vector<int>& nums, int n, int s, vector<int>& cur, vector<vector<int>>& ans) { if (n == cur.size()) { ans.push_back(cur); return; } for (int i = s; i < nums.size(); ++i) { cur.push_back(nums[i]); dfs(nums, n, i + 1, cur, ans); cur.pop_back(); } } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# Author: Huahua, running time: 60 ms class Solution: def subsets(self, nums): ans = [] def dfs(n, s, cur): if n == len(cur): ans.append(cur.copy()) return for i in range(s, len(nums)): cur.append(nums[i]) dfs(n, i + 1, cur) cur.pop() for i in range(len(nums) + 1): dfs(i, 0, []) return ans |
Implementation 2: Binary
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua, running time: 4 ms class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { const int n = nums.size(); vector<vector<int>> ans; for (int s = 0; s < 1 << n; ++s) { vector<int> cur; for (int i = 0; i < n; ++i) if (s & (1 << i)) cur.push_back(nums[i]); ans.push_back(cur); } return ans; } }; |
Python3
|
1 2 3 4 5 |
# Author: Huahua, 40 ms class Solution: def subsets(self, nums): n = len(nums) return [[nums[i] for i in range(n) if s & 1 << i > 0] for s in range(1 << n)] |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment