建企业网站价格,二级域名网站价格,广西短视频运营是,网站建设方案报价题目
给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。示例 1#xff1a;
输入#xff1a;n 4, k 2
输出#xff1a;
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]示例 2#xff1a;
输入#xff1a;n 1, k 1
…题目
给定两个整数 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 ndef 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-i1len(res) k - n-i1 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]))总结
时常感叹别人为什么这么厉害
