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

// create a lambda function: backtracking and enumerate all subsets
// Time Complexity: O(N x 2^N).
// Space Complexity: O(N).
vector<vector<int>> subsets(vector<int>& nums) {
	vector<vector<int>> result;
	vector<int> path;
	function<void<int>> backtracking = [&](int start) {
		int n = static_cast<int>(nums.size());
		result.push_back(path);
		for (int i = start; i < n; ++i) {
			path.push_back(nums[i]);
			backtracking(nums, i + 1);
			path.pop_back();
		}
	};
	backtracking(0);
	return result;
}