Ruby solution with binary digits (AC, explained)


  • 0
    N

    The idea is to generate unique combinations of bits, that is, a set of binary digits, each made of nums.size bits. For example, for nums = [1, 2, 3] the set of binary digits is ---
    [0, 0, 0]
    [0, 0, 1]
    [0, 1, 0]
    [0, 1, 1]
    [1, 0, 0]
    [1, 0, 1]
    [1, 1, 0]
    [1, 1, 1]

    Since the generated combinations are unique, indexes of "1"can be used to generate unique combinations items from nums. Example is, [1, 1, 0] -> [1, 2] and [1, 1, 1] -> [1, 2, 3].

    return [] if nums.empty?
    result = []
    nums.sort!
    for i in 0...2**nums.size do 
    
        #arr is to store 1s and 0s for current i
        arr = i.to_s(2).split("").to_a.map{|i| i.to_i} 
            
            #i should occupy nums.size "bits"
            until arr.size >= nums.size do
                arr = [0] + arr   #or arr.unshift(0)
            end
            
            temp = [] #will store apt combination of items from nums array
            index = 0 #index of current element in arr
            
            arr.each do |item|
                if (item == 1)
                    temp << nums[index] 
                end
                index += 1    
            end
            
            result << temp
    end
    result

Log in to reply
 

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