Leetcode Subsets Problem Solution

In this 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.

Problem solution in Python.

dp = collections.defaultdict(list)
dp[1] = [[i] for i in nums]
 
for x in xrange(2,len(nums)+1):
    for up in dp[x-1]:
        for i in xrange(nums.index(up[-1])+1,len(nums)):
            dp[x].append(up + [nums[i]])
 
ans = [[]]
for val in dp.values():
    for v in val:
        ans.append(v)
 
return ans

Problem solution in Java.

class Solution 
{
    public List<List<Integer>> subsets(int[] nums) 
    {
        List<List<Integer>> r = new ArrayList();
        find(r, nums, 0, new ArrayList());
        return r;
    }
 
    
    void find(List<List<Integer>> r, int[] nums, int pos, List<Integer> cur)
    {
        if (pos == nums.length)
        {
            r.add(new ArrayList(cur));
            return;
        }
        
        // skip this number
        find(r, nums, pos + 1, cur);
        
        // add this number
        int n = cur.size();
        cur.add(nums[pos]);
        find(r, nums, pos + 1, cur);
        cur.remove(n);
    }
}

Problem solution in C++.

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans = {{}};
        for (int num : nums) {
            int n = ans.size();
            for (int i = 0; i < n; ++i) {
                vector<int> s = ans[i];
                s.push_back(num);
                ans.push_back(s);
            }
        }
        return ans;
    }
};

Problem solution in C.

int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) {
    int **result;
    int *colSize;
    int i = 0;
    int temp = 0;
    int count = 0;
    int max = pow(2,numsSize);
    int *matrix = calloc(numsSize, sizeof(int));
    *returnSize = max;
    result = calloc(*returnSize,sizeof(int *));
    colSize = calloc(*returnSize, sizeof(int));
    for(i = 0; i < *returnSize; i++){
        result[i] = malloc(numsSize*sizeof(int));
    }
    i = 0;
    while(i < max){
        if(i==0){
            colSize[i] = 0;
            result[i] = NULL;
        }
        else if(i==1){
            colSize[i] = 1;
            result[i] = malloc(colSize[i]*sizeof(int));
            result[i][0] = nums[i-1];
        }else{
            temp = i;
            count = 0;
            while(temp != 0){
                if(temp%2==1){
                    colSize[i]++;
                    result[i] = realloc(result[i],sizeof(int)*colSize[i]);
                    result[i][colSize[i]-1] = nums[count];
                }
                count++;
                temp/=2;
            }//end of temp
        }
        i++;
    }
    *columnSizes = colSize;
    return result;
}