Table of Contents
Given a set of distinct integers nums, return all possible subsets (the power set) of the set.
Sample Input/Output:
Let’s consider a sample input:
nums = [1, 2, 3]
Expected Output:
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Explanation:
For the given input [1, 2, 3], all possible subsets are [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]].
Time and Space Complexity:
The time complexity of the solution will be O(2^N) because there are 2^N possible subsets for a set of N elements. For each element, we have two choices: include it in the subset or exclude it.
The space complexity will be O(2^N) to store all the subsets.
Now, let’s implement the solution in C++:
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
vector<int> subset;
// Helper function to backtrack and generate subsets
// start is used to keep track of the current position in the input array
// subset is the current subset being built
// result is the final list of subsets
void backtrack(int start, vector<int>& subset, vector<vector<int>>& result) {
result.push_back(subset); // Add the current subset to the result
// Continue building subsets by adding the next element to the subset
for (int i = start; i < nums.size(); ++i) {
subset.push_back(nums[i]);
backtrack(i + 1, subset, result);
subset.pop_back(); // Remove the last element to backtrack and build other subsets
}
}
backtrack(0, subset, result); // Start building subsets from the beginning of the input array
return result;
}
int main() {
vector<int> nums = {1, 2, 3};
vector<vector<int>> result = subsets(nums);
cout << "Subsets:\n";
for (const vector<int>& subset : result) {
cout << "[";
for (int num : subset) {
cout << num << " ";
}
cout << "]" << endl;
}
return 0;
}
In this implementation, we use backtracking to generate all possible subsets. The backtrack function is a recursive function that starts building subsets from the start position in the input array nums. It explores two options for each element at index i: either include it in the current subset or exclude it. When a valid subset is formed, it is added to the result.
The main function demonstrates the usage of subsets by finding all possible subsets for the given input nums.
The output for the provided test case will be:
Subsets:
[]
[1 ]
[1 2 ]
[1 2 3 ]
[1 3 ]
[2 ]
[2 3 ]
[3 ]