题目

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

注意：本题与主站 77 题相同： 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

LCR 080. 组合 - 力扣（LeetCode）

题解

思路：回溯解决，使用一个perm来记录单个的情况。回溯时记得递归出来之后删去已有的改变。java传递list时是地址，因此需要result.add(new ArrayList<>(perm))，不能直接add

剪枝：当发现n剩下的数量不足以撑起k-perm.size()的时候，可以剪去。

注意是从1到n的，不是0到n-1.

代码：

class Solution {List<Integer> perm;List<List<Integer>> result;int n,k;public List<List<Integer>> combine(int n, int k) {perm =new ArrayList<>();result = new ArrayList<>();this.n=n;this.k=k;dfs(1);return result;}private void dfs(int j) {if(perm.size()==k) {result.add(new ArrayList<>(perm));return;}for(int i=j;i<=n;i++) {// 剪枝：如果剩余的个数不够填充list了，直接返回即可if(n-i+1 < k-perm.size()) return;perm.add(i);dfs(i+1);perm.remove(perm.size()-1);}}
}

tips：写法，可以将result，perm，n，k等写在属性值里，通过函数构造进去，这样dfs就不用传多个值了。