Subsets Problem Solution [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 :

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

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

Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment