首頁猿問使用遞歸查找所有 k 個子集

使用遞歸查找所有 k 個子集

Python

慕桂英3389331 2021-09-11 19:30:43

我正在嘗試找到一種方法來創(chuàng)建一個遞歸算法，該算法將給出一組數(shù)字 (0 -> n) 的所有 k 長度子集，但我無法將列表作為參數(shù)發(fā)送給函數(shù)。最終我想返回一個列表列表我想從最后開始，使用某種DP。我嘗試過的所有東西都沒有接近它

查看完整描述

1 回答

ITMISS

TA貢獻1871條經(jīng)驗獲得超8個贊

首先處理最后一個元素 ( n-1) 允許您不使用給定的函數(shù)簽名傳遞中間結(jié)果：

def subsets(n, k):

if n < k or k < 0:

return []

if k == n:

return [list(range(k))]

return subsets(n-1, k) + [s+[n-1] for s in subsets(n-1, k-1)]

>>> subsets(3, 2)

[[0, 1], [0, 2], [1, 2]]

>>> subsets(4, 2)

[[0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]]

>>> subsets(4, 3)

[[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]]

反對回復(fù) 2021-09-11

關(guān)注

舉報

0/150

提交

取消

購課補貼
聯(lián)系客服咨詢優(yōu)惠詳情

慕課網(wǎng)APP
您的移動學(xué)習(xí)伙伴

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號