print('Løsning 1')

def subsets(L, k):
    if k == 0:
        return [[]]
    if k > len(L):
        return []
    if k == len(L):
        return [L.copy()]

    head = L[0]
    tail = L[1:]
    answer = subsets(tail, k)
#    answer += [[head] + subset for subset in subsets(tail, k - 1)]
    for subset in subsets(tail, k - 1):
        answer.append([head] + subset)
    return answer

print(subsets([1,2,3,4,5], 3))

# Correct answer: [[3, 4, 5], [2, 4, 5], [2, 3, 5], [2, 3, 4], [1, 4, 5],
#                  [1, 3, 5], [1, 3, 4], [1, 2, 5], [1, 2, 4], [1, 2, 3]]

print('Løsning 2')

def subsets(L, k, indent=0):
#    print('.' * indent + f'subsets({L}, {k})')
    if k == 0:
        answer = [[]]
    elif k > len(L):
        answer = []
#    elif k == len(L):
#        answer = [L.copy()]
    else:
        #head = L[0]
        #tail = L[1:]
        head, *tail = L
        answer = subsets(tail, k, indent=indent + 1)
#        answer += [[head] + subset for subset in subsets(tail, k - 1)]
        for subset in subsets(tail, k - 1, indent=indent + 1):
            answer.append([head] + subset)

#    print('.' * indent + f'subsets({L}, {k}) = {answer}')
    return answer

print(subsets([1,2,3,4,5], 3))

#print(subsets([1,2,3], 2))

# Correct answer: [[3, 4, 5], [2, 4, 5], [2, 3, 5], [2, 3, 4], [1, 4, 5],
#                  [1, 3, 5], [1, 3, 4], [1, 2, 5], [1, 2, 4], [1, 2, 3]]



print('Løsning 3')

def subsets(L, k):
    if k == 0:
        return [[]]
    if k > len(L):
        return []
    head, *tail = L
    return (subsets(tail, k) +
            [[head] + subset for subset in subsets(tail, k - 1)])

print(subsets([1,2,3,4,5], 3))

#print(subsets([1,2,3], 2))

print('Løsning 4')

# L = (x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x)
#      |---------- S = subsets of size <= k   ------|  i

def subsets(L, k):
    S = [[]]
    for i in range(len(L)):
        for subset in S.copy():
            #print(S)
            if len(subset) < k:
                S.append(subset + [L[i]])

    answer = [subset for subset in S if len(subset) == k]
    return answer 

print(subsets([1,2,3,4,5], 3))

print('Løsning 5')

def subsets(L, k):
    S = [[]]  # alle løsninger med 0 elementer
    for _ in range(k):
        # print(S)
        S_new = []
        for subset in S:
            for x in L:
                if subset == [] or x > subset[-1]:
                    new_subset = subset + [x]
                    S_new.append(new_subset)
        S = S_new

    return S

print(subsets([1,2,3,4,5], 3))


print('Løsning 6')

def subsets(L, k):
    S = [[]]  # alle løsninger med 0 elementer
    for _ in range(k):
        print(S)
        S = [[*subset, x]
             for subset in S
             for x in L
             if subset == [] or x > subset[-1]]

    return S

print(subsets([1,2,3,4,5], 3))