Subsets Leetcode Solution
Subsets 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 :
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Subsets Leetcode Problem Solution :
Constraints :
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- All the numbers of nums are unique.
Example:
- Input: nums = [0]
- Output: [[],[0]]
Idea to solve:
- This is a very common problem in backtracking which is known by Take it or Leave it.
- All we need to do is to create all possible sets, so for each node we will stand over it, we will have two main choices, one to create a set with that node, and the other is to create a set without this node, so after we finsh we will find that we have created all possible unique sets.
Approach:
The solution depends on two main functions:
backTracking (res, nums, i, sz, sent)
parameters and return type
- This is a void function, which return nothing.
- It is a recursive one.
- res is the result matrix, we sent it by reference to store the sets in it.
- nums, is the given integer list.
- i which is the current index.
- sz, the size of the nums, but I sent it to not get the size in each call.
- sentr: it is a vector in which we insert the elements, till we reach the base case, then we insert the whole vector at the last case.
Base Case:
if the current index == size of the nums, then we have exceeded the array, and passed over all elements, so we just need to insert the sentr vector in the result matrix.
Recursive Logic:
- Insert the nums[i] in the sentr vector.
- Call the backtracking function, and in each call, send i + 1.
- After coming back, pop that element.
- Call the backtracking function again.
Complexity:
- Time complexity: O(N)
- Space complexity: O(N)
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
#define DPSolver ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
void backTracking(vector< vector< int>> &res, const vector< int> &nums, int i, int sz, vector< int> &sentr)
{
if (i == sz)
{
res.push_back(sentr);
return;
}
sentr.push_back(nums[i]);
backTracking(res, nums, i + 1, sz, sentr);
sentr.pop_back();
backTracking(res, nums, i + 1, sz, sentr);
}
vector< vector< int>> subsets(vector< int> &nums)
{
DPSolver;
vector> res;
int sz = nums.size();
vector< int> sent;
backTracking(res, nums, 0, sz, sent);
return res;
}
};
Java
import java.util.ArrayList;
import java.util.List;
class Solution {
void backTracking(List< List< Integer>> res, List< Integer> nums, int i, int sz, List< Integer> sentr) {
if (i == sz) {
res.add(new ArrayList< >(sentr));
return;
}
sentr.add(nums.get(i));
backTracking(res, nums, i + 1, sz, sentr);
sentr.remove(sentr.size() - 1);
backTracking(res, nums, i + 1, sz, sentr);
}
List> subsets(List< Integer> nums) {
List< List< Integer>> res = new ArrayList< >();
int sz = nums.size();
List< Integer> sent = new ArrayList< >();
backTracking(res, nums, 0, sz, sent);
return res;
}
} Python
class Solution:
def backTracking(self, res, nums, i, sz, sentr):
if i == sz:
res.append(sentr)
return
sentr.append(nums[i])
self.backTracking(res, nums, i + 1, sz, sentr)
sentr.pop()
self.backTracking(res, nums, i + 1, sz, sentr)
def subsets(self, nums):
res = []
sz = len(nums)
sent = []
self.backTracking(res, nums, 0, sz, sent)
return res
Login/Signup to comment