# Time complexity: O(n * log(n))

def generate_all_combinations(arr, target):

    def helper(sub,index,partial,result,target,rem_sum):

        if target==0:
            result.append(partial)
            return result

        if index==len(sub) or target<0 or target>rem_sum:
            return result

        # find count of sub[index]
        end = index
        count = 0
        while end<len(sub) and sub[end]==sub[index]:
            end+=1
            count+=1

         # include i occurences of sub[index] in partial
        for i in range(0, count+1):
            helper(sub, end, partial + i*[sub[index]], result,target - i*sub[index], rem_sum - count*sub[index])

        return result

    arr.sort()
    out=helper(arr,0,[],[],target,sum(arr))
    return out