Leetcode Subsets problem solution

Apr 24, 2023

In the Leetcode 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 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.

Solution in C Programming

``````//global variable count.
static count=0;

int** combine(int* nums, int numsSize, int k, int** result, int* retcolsizes){
//max size for all conditions is 184756, for n=20 , k=10.
//Seems the task max is n=20, k=16, we set the size to 4865.
int stack[10]={0};
int top=-1;
int kTemp=k;
int target=-1;
while(1)
{
//there are no more element to be push ==> no more condition for result.
if (target==numsSize-1 && kTemp != 0)
break;
//still need to push ==> push element.
else if (kTemp!=0)
{
stack[++top] = ++target;
kTemp--;
}
//put new result and prepare another solution
else
{
result[count]=malloc(sizeof(int)*k);
retcolsizes[count]=k;
for (int i=0; i<=top ; i++)
result[count][i]=nums[stack[i]];
count++;

//pop element
//if stack store numsSize-1, pop until non-continuous number, then pop one.
if (stack[top]==numsSize-1)
{
top--; kTemp++;
while (top>=0 && stack[top]==stack[top+1]-1)
{
top--; kTemp++;
}

//can't pop element  ==> no more condition for result.
if (top==-1)
break;

//set target to pop number +1,
target=stack[top];
top--; kTemp++;
}
//pop one number.
else
{
top--; kTemp++;
}
}
}
return result;
}

/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
//max size is 2*(10!/(0!+10!)+10!/(1!+9!)+10!/(2!+8!)+10!/(3!+7!)+10!/(4!+6!)) + 10!/(5!+5!)
//=1024, for numsSize<=10.
int** result= malloc(sizeof(int*)*1024);
int* retcolsizes = malloc(sizeof(int)*1024);
*returnColumnSizes=retcolsizes;
count=0;

//put null subset
result[count]=malloc(sizeof(int)*0);
retcolsizes[count]=0;
result[count]=NULL;
count++;

//Call modified combine function from 77. Combinations
for (int i=1 ; i<=numsSize ; i++)
{
combine(nums, numsSize, i, result, retcolsizes);
}
(*returnSize)=count;
return result;
}``````

Solution in C++ Programming

``````class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> subset;
insertElements(nums, 0, res, subset);
return res;
}

void insertElements(vector<int>& nums, int index, vector<vector<int>>& res, vector<int>& subset) {
if (index == nums.size()) {
res.push_back(subset);
return;
}
insertElements(nums, index + 1, res, subset);
subset.push_back(nums[index]);
insertElements(nums, index + 1, res, subset);
subset.pop_back();
}
};``````

Solution in Java Programming

``````class Solution {
public List<List<Integer>> subsets(int[] S) {
List<List<Integer>> result = new ArrayList<List<Integer>>();

if(S.length == 0){
return result;
}

Arrays.sort(S);
dfs(S, 0, new ArrayList<Integer>(), result);
return result;
}

public void dfs(int[] s, int index, List<Integer> path, List<List<Integer>> result){

for(int i = index; i < s.length; i++){
dfs(s, i+1, path, result);
path.remove(path.size()-1);
}
}
}``````

Solution in Python Programming

``````class Solution:
def subsets(self, nums):
out = [[]]
while nums:
curr = nums.pop()
out.extend([c + [curr] for c in out])

return out``````

Solution in C# Programming

``````public class Solution
{
public IList<IList<int>> Subsets(int[] nums)
{
List<IList<int>> answer = new List<IList<int>>();
int length = nums.Length;
int[] indexes = new int[length];//Create a buffer for the indexes

answer.Add(new List<int>());//We always have the empty set

for(int k = 1; k <= length; k++)
{
int maxIndex = k - 1;
int index = maxIndex, delta = length - k;

for (int i = 0; i < k; i++)
{
indexes[i] = i;//Initial values
}

while (index > -1)
{
//Add current state of counters to answer
IList<int> row = new List<int>();
for(int i=0; i < k; i++)
{
}

//find counter to increment
while (index > -1 && indexes[index] >= index + delta) --index;

if (index > -1)
{
++indexes[index];

for (int i = index + 1; i < k; i++)
{
indexes[i] = indexes[i - 1] + 1;//reset counters
}

//find new counter
while (index < maxIndex && indexes[index] < index + delta) ++index;
}
}
}

}
}``````

By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.