Blogs Hub

Subsets - Array - Medium - LeetCode - MiniTV

Subsets - Array - Medium - LeetCode - मिनी टीवी

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

public class Solution {
    IList<IList<int>> res = new List<IList<int>>();     
    public IList<IList<int>> Subsets(int[] nums) {
        Array.Sort(nums);
        res.Add(new List<int>());
        var ans = new List<int>();        
        Helper(nums,ans, 0);
        return res;
    }
    
    private void Helper(int[] nums, List<int> ans, int index){
        if(ans.Count() > nums.Length){
            return;
        }
        
        if(ans.Count()>0){
            CheckAndAdd(ans);
        }
        
        for(int i=index;i< nums.Length;i++){
            if(ans.Contains(nums[i])){
                continue;
            }
            ans.Add(nums[i]);
            Helper(nums, ans, i+1);
            ans.RemoveAt(ans.Count()-1);
        }
    }
    
    private void CheckAndAdd(List<int> ans){
        res.Add(ans.ToArray().ToList());       
    }
}

Time Complexity: O(2^n)

Space Complexity: O(n) // for stack trace