Backtracking: toate submulțimile
Scrie funcția submultimi(lista) care returnează toate submulțimile, în ordinea generării prin backtracking „de la start încolo”: salvezi submulțimea curentă, apoi încerci fiecare element de la start la final. Fără itertools.
- Într-o funcție internă
backtrack(start):rezultat.append(curenta[:]). - Pentru
ide lastart:append,backtrack(i + 1),pop(). - Trebuie să apară: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]], [[]], 32.
lista, rezultat și curenta din funcția exterioară, deci nu trebuie să le trimiți ca parametri.def submultimi(lista):
rezultat = []
curenta = []
def backtrack(start):
rezultat.append(curenta[:])
for i in range(start, len(lista)):
curenta.append(lista[i])
backtrack(i + 1)
curenta.pop()
backtrack(0)
return rezultat
print(submultimi([1, 2, 3]))
print(submultimi([]))
print(len(submultimi([1, 2, 3, 4, 5])))


