代码随想录Day20 | Leetcode77 组合

题目

给定两个整数 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]))

总结

时常感叹，别人为什么这么厉害