def generate_subsets(n, m):
    subsets = set()
    subsets.add( (0, 0, frozenset()) )
    desired_total = (1 + n*m) * n / 2
 
    for number in xrange(1, n*m + 1):
        new_subsets = subsets.copy()
        for size, total, numbers in subsets:
            new_size = size + 1
            if new_size > n:
                continue
            new_total = total + number
            if new_total > desired_total:
                continue
            new_numbers = numbers | frozenset( [number] )
            new_subsets.add( (new_size, new_total, new_numbers) )
        subsets = new_subsets
 
    return [ subset for (size, total, subset) in subsets 
            if size == n and total == desired_total ]
 
def print_covers(subsets, selected_subsets, not_used_numbers):
    for subset_index, subset in enumerate(subsets):
        if not subset <= not_used_numbers:
            continue
        new_not_used_numbers = not_used_numbers - subset
        new_selected_subsets = selected_subsets + [ subset ]
        if new_not_used_numbers:
            new_subsets = subsets[subset_index:]
            print_covers(new_subsets, new_selected_subsets, new_not_used_numbers)
        else:
            print ' '.join(map(lambda s: "{%s}" % (", ".join(map(str, s))), new_selected_subsets))
 
n = 3
m = 3
 
subsets = generate_subsets(n, m)
print_covers( subsets, [], frozenset(range(1, m*n + 1)) )
 

CmRlZiBnZW5lcmF0ZV9zdWJzZXRzKG4sIG0pOgogICAgc3Vic2V0cyA9IHNldCgpCiAgICBzdWJzZXRzLmFkZCggKDAsIDAsIGZyb3plbnNldCgpKSApCiAgICBkZXNpcmVkX3RvdGFsID0gKDEgKyBuKm0pICogbiAvIDIKCiAgICBmb3IgbnVtYmVyIGluIHhyYW5nZSgxLCBuKm0gKyAxKToKICAgICAgICBuZXdfc3Vic2V0cyA9IHN1YnNldHMuY29weSgpCiAgICAgICAgZm9yIHNpemUsIHRvdGFsLCBudW1iZXJzIGluIHN1YnNldHM6CiAgICAgICAgICAgIG5ld19zaXplID0gc2l6ZSArIDEKICAgICAgICAgICAgaWYgbmV3X3NpemUgPiBuOgogICAgICAgICAgICAgICAgY29udGludWUKICAgICAgICAgICAgbmV3X3RvdGFsID0gdG90YWwgKyBudW1iZXIKICAgICAgICAgICAgaWYgbmV3X3RvdGFsID4gZGVzaXJlZF90b3RhbDoKICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgIG5ld19udW1iZXJzID0gbnVtYmVycyB8IGZyb3plbnNldCggW251bWJlcl0gKQogICAgICAgICAgICBuZXdfc3Vic2V0cy5hZGQoIChuZXdfc2l6ZSwgbmV3X3RvdGFsLCBuZXdfbnVtYmVycykgKQogICAgICAgIHN1YnNldHMgPSBuZXdfc3Vic2V0cwoKICAgIHJldHVybiBbIHN1YnNldCBmb3IgKHNpemUsIHRvdGFsLCBzdWJzZXQpIGluIHN1YnNldHMgCiAgICAgICAgICAgIGlmIHNpemUgPT0gbiBhbmQgdG90YWwgPT0gZGVzaXJlZF90b3RhbCBdCgpkZWYgcHJpbnRfY292ZXJzKHN1YnNldHMsIHNlbGVjdGVkX3N1YnNldHMsIG5vdF91c2VkX251bWJlcnMpOgogICAgZm9yIHN1YnNldF9pbmRleCwgc3Vic2V0IGluIGVudW1lcmF0ZShzdWJzZXRzKToKICAgICAgICBpZiBub3Qgc3Vic2V0IDw9IG5vdF91c2VkX251bWJlcnM6CiAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgbmV3X25vdF91c2VkX251bWJlcnMgPSBub3RfdXNlZF9udW1iZXJzIC0gc3Vic2V0CiAgICAgICAgbmV3X3NlbGVjdGVkX3N1YnNldHMgPSBzZWxlY3RlZF9zdWJzZXRzICsgWyBzdWJzZXQgXQogICAgICAgIGlmIG5ld19ub3RfdXNlZF9udW1iZXJzOgogICAgICAgICAgICBuZXdfc3Vic2V0cyA9IHN1YnNldHNbc3Vic2V0X2luZGV4Ol0KICAgICAgICAgICAgcHJpbnRfY292ZXJzKG5ld19zdWJzZXRzLCBuZXdfc2VsZWN0ZWRfc3Vic2V0cywgbmV3X25vdF91c2VkX251bWJlcnMpCiAgICAgICAgZWxzZToKICAgICAgICAgICAgcHJpbnQgJyAnLmpvaW4obWFwKGxhbWJkYSBzOiAieyVzfSIgJSAoIiwgIi5qb2luKG1hcChzdHIsIHMpKSksIG5ld19zZWxlY3RlZF9zdWJzZXRzKSkKCm4gPSAzCm0gPSAzCgpzdWJzZXRzID0gZ2VuZXJhdGVfc3Vic2V0cyhuLCBtKQpwcmludF9jb3ZlcnMoIHN1YnNldHMsIFtdLCBmcm96ZW5zZXQocmFuZ2UoMSwgbSpuICsgMSkpICkK