Finding set of pairs that correspond to list of sums

Given two lists of numbers and a list of totals (none in any particular order):

a = [1,2,3]
b = [4,5,6]
c = [6,7,8]

How can I find all sets of pairs d where d[k] = (a[i], b[j]) such that c[k] = a[i] + b[j] where pairs are used from a and b without replacement? (all lists can have duplicates)

d = [(1,5), (3,4), (2,6)]
d = [(2,4), (1,6), (3,5)]

For c = [7,7,7]:

d = [(1,6), (2,5), (3,4)]

(1 answer because all permutations are essentially equivalent)

I'd like to do this with lists of length ~500, so a naive matching/backtracking search is out of the question.