算法
时间复杂度: O(2^n)
总空间复杂度: O(2^n)
额外空间复杂度: O(n)
C++代码
class Solution {
public:
vector<vector<int>> subsets(const vector<int> &nums) {
n = static_cast<int>(nums.size());
res.resize(1 << n);
resIndex = 0;
pNums = &nums;
path.resize(n);
subsetsDfs(0, 0);
return res;
}
private:
void subsetsDfs(int numIndex, const int pathIndex) {
const vector<int> &nums = *pNums;
res[resIndex++] = move(vector(path.begin(), path.begin() + pathIndex));
for (; numIndex < n; ++numIndex) {
path[pathIndex] = nums[numIndex];
subsetsDfs(numIndex + 1, pathIndex + 1);
}
}
int n;
vector<vector<int>> res;
int resIndex;
const vector<int> *pNums;
vector<int> path;
};
Java代码
未完待续
Python3代码
class Solution:
def subsets(self, nums: list) -> list:
self.n = len(nums)
self.res = [0] * (1 << self.n)
self.resIndex = 0
self.nums = nums
self.path = [0] * self.n
self.subsetsDfs(0, 0)
return self.res
def subsetsDfs(self, numIndex: int, pathIndex: int) -> None:
self.res[self.resIndex] = self.path[:pathIndex]
self.resIndex += 1
for numIndex in range(numIndex, self.n):
self.path[pathIndex] = self.nums[numIndex]
self.subsetsDfs(numIndex + 1, pathIndex + 1)
Go代码
未完待续