Subsets Problem Solution: 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]]
Table of Contents
Subsets Problem Solution [Leetcode]
Problem Solution In Python
class Solution:
def _subsets(self, nums:List[int], current: List[int], index:int):
if index>=len(nums):
self.sol.append(current)
return
# solution adding the nums[index]
self._subsets(nums, current+[nums[index]], index+1)
# solution ignoring nums[index]
self._subsets(nums, current, index+1)
def subsets(self, nums: List[int]) -> List[List[int]]:
self.sol = []
self._subsets(nums,[], 0)
return self.sol
Problem Solution In Java
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
boolean[] used = new boolean[nums.length];
rec(res, new ArrayList<>(), nums, 0, used);
return res;
}
private void rec(List<List<Integer>> res, List<Integer> temp, int[] nums, int idx, boolean[] used){
res.add(new ArrayList<>(temp));
if(temp.size() == nums.length){
return;
}
for(int i = idx; i < nums.length; i++){
if(used[i]){
continue;
}
temp.add(nums[i]);
used[i] = true;
rec(res, temp, nums, i, used);
used[i] = false;
temp.remove(temp.size() - 1);
}
}
}
Problem Solution In C++
class Solution {
public:
vector<vector<int>> ans;
void check(vector<int> nums,int start,vector<int> &v)
{
ans.push_back(v);
for(int i=start;i<nums.size();i++)
{
v.push_back(nums[i]);
check(nums,i+1,v);
v.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> v;
check(nums,0,v);
return ans;
}
};
Problem Solution In C
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
if (nums == NULL || numsSize == 0)
return NULL;
int outputSize = pow(2, numsSize);
*returnSize = outputSize;
int **result = (int **)malloc(outputSize * sizeof(int*));
for (int i = 0; i < outputSize; i++)
result[i] = (int *)malloc(numsSize * sizeof(int*));
*returnColumnSizes = (int*)calloc(*returnSize, sizeof(int));
for (int i = 0; i < outputSize; i++)
{
int cnt = 0;
for (int j = 0; j < numsSize; j++)
{
int element = pow(2, j);
if (element & i)
{
result[i][cnt] = nums[j];
cnt++;
}
}
(*returnColumnSizes)[i] = cnt;
}
return result;
}