題目

給定兩個整數 n 和 k，返回范圍 [1, n] 中所有可能的 k 個數的組合。你可以按 任何順序 返回答案。示例 1：
輸入：n = 4, k = 2
輸出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]示例 2：
輸入：n = 1, k = 1
輸出：[[1]]提示：
1 <= n <= 20
1 <= k <= n

思路

學到了兩種非常有用的思路

代碼

class Solution:"""給定兩個整數 n 和 k，返回范圍 [1, n] 中所有可能的 k 個數的組合。你可以按 任何順序 返回答案。示例 1：輸入：n = 4, k = 2輸出：[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]示例 2：輸入：n = 1, k = 1輸出：[[1]]提示：1 <= n <= 201 <= k <= n"""def combine1(self, n, k):result = []res = []def dfs(i):"""在[1,i]中獲取d個數i < d:表示剩下的數量仍小于需要取的數量，可以不用遞歸，直接返回"""d = k - len(res) # 還需要取d個數# if i< d:return,該條件可換為如下的[d-1, i]if d == 0:result.append(res.copy())return# 從后往前，僅取從i往前的d個數，從前往后的返回條件是：n-i+1+len(res) < k -> n-i+1 < dfor j in range(i, d-1, -1):res.append(j)dfs(j-1)res.pop()dfs(n)return resultdef combine(self, n, k):result = []res = []def dfs(i):"""在[1,i]中獲取d個數i < d:表示剩下的數量仍小于需要取的數量，可以不用遞歸，直接返回"""d = k - len(res) # 還需要取d個數# if i< d:returnif d == 0:result.append(res.copy())return# 不選i,超出d的部分先不選if i > d:dfs(i-1)# 選ires.append(i)dfs(i-1)res.pop()dfs(n)return resultif __name__ == '__main__':test = Solution()n = [4, 1]k = [2, 1]for i in range(len(n)):print(test.combine(n[i], k[i]))print(test.combine1(n[i], k[i]))

總結

時常感嘆，別人為什么這么厲害