Subsets
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
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();
}
}
Follow-up:
Generate all possible subsets of a given array of integers, where each integer can be used more than once.