题目:https://leetcode-cn.com/problems/combinations/
代码:
class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> res = new ArrayList<>(); if (k > n || k <= 0) { //不合法的情况,组合为空 return res; } if (k == 1) { //k为1,则每个数字都是1个组合,共n个组合 for (int i = 1; i <= n; i++) { List<Integer> c = new ArrayList<>(); c.add(i); res.add(c); } } else if (k == n) { //k==n,则所有数字是1个组合,共1个组合 List<Integer> c = new ArrayList<>(); for (int i = 1; i <= n; i++) { c.add(i); } res.add(c); }else{ //k<n,则分2种情况 //1、组合中没n,则剩下n-1个数中需要选k个数 res = this.combine(n - 1, k); //2、组合中必有n,则剩下n-1个数中需要选k-1个数 List<List<Integer>> cList = this.combine(n - 1, k - 1); for (List<Integer> c : cList) { c.add(n); } res.addAll(cList); } return res; } }
题目要求从n个数中选出k个数的所有组合,我们可以分情况来获取。
1、诸如k<=0或者k>n这种不合法的情况直接返回空结果。
2、k=1的情况,那就是每一个数字都是1个组合,直接遍历1-n,每一个数做一个组合返回。
3、k=n的情况,那就是从n个数选n个数,即所有的数一起是一个组合,遍历1-n,所有的数做一个组合返回。
4、k<n的情况,这个是常规的操作,我们可以考虑使用递归,分2种情况处理。
a、组合中一定没有n,则k个数需要从剩下的n-1个数中选取,组合结果为C(n-1,k)
b、组合中一定有n,则还剩k-1个数需要从剩下的n-1个数中选取,组合结果为C(n-1,k-1)
所以4这种情况下的组合结果最终为:C(n,k)=C(n-1,k)+C(n-1,k-1)。这里的C就是我们的递归函数combine,将上述1到4点要求转化成代码即为本题解。