专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
一网友在网上询问：发现leader是大专毕业，怎么办？他大专和你有啥关系啊。leader学历是大专，可能人家来的早，并且leader不一定需要很高的技术，只要会管理就行。技术需要的是智商，管理需要的是情商，智商高的不一定情商高，所以leader的学历不如你很正常。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第77题：组合。
问题描述
来源：LeetCode第77题
难度：中等
给定两个整数 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
问题分析
这题返回从 1 到 n 中所有 k 个数的组合，所谓的组合也就是从数组中选择 k 个数，这种选择只是其中的一个组合。我们知道排列是有顺序的，但组合是没有顺序的，比如[1,2]和[2,1]只能算一个组合。组合选择的过程我们可以把它看作是一棵树，如下图所示：
因为每个数字在每个组合中只能选择一次，所以选择当前数字的时候，下一步只能选择他后面的数字，否则就会出现类似于[1,2]和[2,1]这种重复的组合。当选择个数达到 k 个的时候就不要再往下选了，然后把这个组合添加到最终的集合中，这是一道回溯算法问题，代码非常简单。
JAVA：
public List
> combine( int n, int k) { List > ans = new ArrayList<>(); dfs(ans, new ArrayList<>(k), n, k, 1); return ans; } private void dfs(List > ans, List path, int n, int k, int start) { if (path.size() == k) { ans.add( new ArrayList<>(path)); return; } for ( int i = start; i <= n; i++) { path.add(i); // 选择 dfs(ans, path, n, k, i + 1); // 递归到下一层 path.remove(path.size() - 1); // 撤销选择 } }C++：
public: vector
> combine(int n, int k) { vector
> ans; vector
path; dfs(ans, path, n, k, 1); return ans; } void dfs(vector
> &ans, vector
&path, int n, int k, int start) { if (path.size() == k) { ans.emplace_back(path); return; } for (int i = start; i <= n; i++) { path.emplace_back(i);// 选择 dfs(ans, path, n, k, i + 1);// 递归到下一层 path.pop_back();// 撤销选择 } }
Python：
def combine(self, n: int, k: int) -> List[List[int]]: ans = [] path = [] def dfs(start: int): if len(path) == k: ans.append(path[:]) return for i in range(start, n + 1): path.append(i) # 选择 dfs(i + 1) # 递归到下一层 path.pop() # 撤销选择 dfs(1) return ans笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴