Three ways to do this(C#)


  • 7
    T
    1. Clone the lists when process each num.

    At beginning, there is only one empty list.

    {{}}

    When we process the first num( use 1 to represent), clone all the existing list, for the cloned list, add the cur num to the list. . Add all the cloned list to the result.

    {{},{1}}

    when we process the second num( use 2 to represent), again clone all existing list, and add cur num to the cloned list. Add all the cloned list to the result.

    {{},{1},{2},{1,2}}

    do this until n.

    public IList<IList<int>> Subsets(int[] nums) 
    {
        Array.Sort(nums);
        IList<IList<int>> res = new List<IList<int>>();
        res.Add(new List<int>());
        if( nums == null || nums.Length == 0 ) return res;
        
        for( int i = 0; i < nums.Length; ++i )
        {
            int count = res.Count;
            for( int j = 0; j < count; ++j )
            {
                List<int> newList = new List<int>( res[j] );
                newList.Add( nums[i] );
                res.Add(newList);
            }
            
        }
        return res;
    }
    

    2.Bit manipulation

    go from 0 to Pow(2, nums.Length)

    0 -> 0000 -> {}

    1 -> 0001 -> {1} // {1} means the list contains the first num in the array nums

    2 -> 0010 -> {2}

    3 -> 0011 -> {2,1}

    .....

    Pow(2, nums.Length) -> ......

    Add all above list to the result.

    public IList<IList<int>> Subsets(int[] nums) 
    {
        Array.Sort(nums);
        
        IList<IList<int>> result = new List<IList<int>>();
        
        int max =  (int)Math.Pow(2, nums.Length);
        for( int counter = 0; counter < max; ++counter )
        {
           IList<int> subSet = new List<int>();
           int mark = 1;
           for( int j = 0; j < nums.Length; ++j ) 
           {
               if( (mark & counter) != 0 )
               {
                  subSet.Add(nums[j]); 
               }
               mark <<= 1;
           }
           
           result.Add(subSet);
        } 
        
        return result;
        
    }
    
    1. Back tracking

    When process each num, there're two choice, add or do not add. If add, a back track is needed.

    public class Solution {
    public IList<IList<int>> Subsets(int[] nums) 
    {
        Array.Sort(nums);
        
        IList<IList<int>> res = new List<IList<int>>();
        IList<int> list = new List<int>();
        
        Subset(res, list, nums, 0);
        
        return res;
    }
    
    private void Subset( IList<IList<int>> res, IList<int> list, int[] nums, int index )
    {
       if( index == nums.Length ) 
       {
           res.Add(new List<int>(list));
           return;
       }
       
       int count = list.Count;
       Subset( res, list, nums,index +1 );
      
       list.Add( nums[index] );
       Subset( res, list, nums,index +1 );
       list.RemoveAt( list.Count -1 );
       
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.