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