Header Ad

Leetcode Subset problem solution

In this Leetcode Subset problem solution we have 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.

Leetcode Subset problem solution


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;
}


Post a Comment

0 Comments