C# recursive approach inspired by Haskell (fastest by Nov 7 2017)


  • 0
    L

    I first attempted to solve this task using Haskell and came up with the function below

    subsets :: [Int] -> [[Int]]
    subsets [] = []
    subsets (a:as) = [[a]] ++ subsets(as) ++ (map (a:) $ subsets as)
    

    The idea is that subsets of given list may be described as union of

    • list with only head element

    • subsets of tail (tail is the list except head element)

    • subsets of tail where each subset is united with head element.

    The only thing about this haskell function is that it doesn't contain an empty set.

    Taking this into account I wrote the following C# code that has been accepted by Leetcode and turned out to be the fastest solution by the moment (Nov 7 2017)
    So I decided to share the solution. It seems it hasn't been discussed yet.

    public IList<IList<int>> Subsets(int[] nums)
    {
        var result = SubsetsRecursive(nums).ToList();
        result.Add(new List<int>());
        return result;
    }
    
    private IEnumerable<IList<int>> SubsetsRecursive(IEnumerable<int> nums)
    {
        if (!nums.Any())
            yield break;
    
        var head = nums.Take(1);
    
        yield return head.ToList();
    
        var tailCombinations = SubsetsRecursive(nums.Skip(1));
    
        foreach (var comb in tailCombinations)
        {
            yield return head.Union(comb).ToList();
    
            yield return comb;
        }
    }
    

Log in to reply
 

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