Intervue featured on Shark TankIntervue featured on Shark Tank - mobile banner

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. It is guaranteed that 0 <= nums.length <= 10.

Constraints:

  • 1 <= nums.length <= 10
  • All elements in nums are unique

Examples:

Input: [1, 2, 3]

Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Explanation: The subsets of [1, 2, 3] are all possible subsets, including the empty subset and the subset containing all elements.

Solutions

Backtracking

Time: O(2^n)Space: O(2^n)

The backtracking approach generates all possible subsets by adding each element to the current subset and then recursively generating all subsets of the remaining elements.

vector<vector<int>> subsets(vector<int>& nums) {
  vector<vector<int>> res;
  vector<int> path;
  backtrack(res, path, nums, 0);
  return res;
}
void backtrack(vector<vector<int>>& res, vector<int>& path, vector<int>& nums, int start) {
  res.push_back(path);
  for (int i = start;
  i < nums.size();
  i++) {
    path.push_back(nums[i]);
    backtrack(res, res, path, nums, i + 1);
    path.pop_back();
  }
}

Difficulty: Medium

Category: Backtracking

Frequency: High

Company tags:

GoogleAmazonMicrosoft