78. Subsets

Question

LeetCode Problem

Given an integer array nums of unique elements, return all possible subsets (the power set) .
The solution set must not contain duplicate subsets. Return the solution in any order .
Example 1:

Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0] Output: [[],[0]]

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique .

Solutions

Use backtracking

void backtracking(const vector<int>& nums, int start, vector<int>& path, vector<vector<int>> &result) {
	result.push_back(path);
	int n = static_cast<int>(nums.size());
	for (int i = start; i < n; ++i) {
		path.push_back(nums[i]);
		backtracking(nums, i + 1, path, result);
		path.pop_back();
	}
}

// generate subsets without duplicate subsets (e.g. [1,2] and [2, 1]) and
// return the subsets. Use backtracking and maintain a path vector to keep
// track backtracking status.\n
// Time Complexity: O(N x 2 ^ N).\n
// Space Complexity: O(N). excluded from the output.
vector<vector<int>> subsets(vector<int>& nums) {
	vector<vector<int>> result;
	vector<int> path;
	backtracking(nums, 0, path, result);
	return result;
}

Use bitmask

  vector<vector<int>> subsets(vector<int> &nums) {
    // use bitmask approach. iterate through all bitmasks, e.g.
    // N = 3, then 001, 010, 011, 100, 101, 110, 111
    // and pick up the nums[i] when the i-th bit is 1.
    // Time Complexity: O(N * 2^N).
    // Space Complexity: O(N) exclude from the result.
    // Edge Case:
    // 1. when n size is 0/1, all processed.
    // Pros: easy and no stack overflow risk.
    // Cons: when n is very large, e.g. larget than 64 which larger than the
    // long long type. This approach will not workable.
    int n = static_cast<int>(nums.size());
    vector<vector<int>> result;
    // when n > 64, means i can not use bimask to store all numbers bits index.
    if (n > 64) return result;
    vector<int> path;
    // pre-allocated n size memory to prevent from frequently allocation.
    path.reserve(n);

    // assmuing use 64bits data to store the bitmasks.
    for (long long mask = 0; mask < (1LL << n); ++mask) {
      path.clear();
      for (int i = 0; i < n; ++i) {
        if (mask & (1 << i)) {
          path.push_back(nums[i]);
        }
      }
      result.push_back(path);
    }
    return result;
  }