算法
时间复杂度: O(2^n)
总空间复杂度: O(2^n)
额外空间复杂度: O(1)
C++代码
class Bit1Count {
public:
Bit1Count() {
for (int i = 255; i >= 0; --i) {
bit1CountArr[i] = bit1Count(i);
}
}
inline int operator()(const unsigned n) const {
return bit1CountArr[n & 0xff] + bit1CountArr[(n >> 8) & 0xff] + //
bit1CountArr[(n >> 16) & 0xff] + bit1CountArr[n >> 24];
}
inline int operator()(const int n) const {
return (*this)(static_cast<unsigned>(n));
}
private:
int bit1Count(int n) const {
int cnt = 0;
for (; n; n &= n - 1) {
++cnt;
}
return cnt;
}
int bit1CountArr[256];
};
extern const Bit1Count bit1Count;
const Bit1Count bit1Count;
class Solution {
public:
static vector<vector<int>> subsets(const vector<int> &nums) {
const int n = static_cast<int>(nums.size());
const int resN = 1 << n;
vector<vector<int>> res(resN);
for (int resIndex = 0; resIndex < resN; ++resIndex) {
vector<int> path(bit1Count(resIndex));
int pathIndex = 0;
for (int bits = resIndex; bits; bits &= bits - 1) {
const int numIndex = bit1Count((bits & (-bits)) - 1);
path[pathIndex++] = nums[numIndex];
}
res[resIndex] = move(path);
}
return res;
}
};
Java代码
未完待续
Python3代码
未完待续
Go代码
未完待续