[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

1 <= n <= 20
1 <= k <= n

1.每个元素有选与不选两种情况，

2.回溯能将选与不选这两种情况都包含

3.递归刚好能满足这个需求

dfs + 回溯代码：
class Solution { public List<List<Integer>> combine(int n, int k) { List<List<
Integer>> end = new ArrayList<>(); List<Integer> mb = new ArrayList<>(); addmbzh
(1, k, end, mb, n); return end; } public static void addmbzh(int x, int k, List<
List<Integer>> end, List<Integer> none, int n) { if(x > n + 1) return; if(none.
addmbzh(x + 1, k, end, none, n); none.remove(none.size() - 1); addmbzh(x + 1, k,
end, none, n); } }

if(none.size() + n - x + 1 < k) return;//即剩下元素不足，直接退出
dfs + 回溯 + 剪枝：
class Solution { public List<List<Integer>> combine(int n, int k) { List<List<
Integer>> end = new ArrayList<>(); List<Integer> mb = new ArrayList<>(); addmbzh
(1, k, end, mb, n); return end; } public static void addmbzh(int x, int k, List<
List<Integer>> end, List<Integer> none, int n) { if(none.size() + n - x + 1 < k)
return;//退出条件 if(none.size() == k) { end.add(new ArrayList<Integer>(none));
() - 1);//回溯（不选） addmbzh(x + 1, k, end, none, n); } }

class Solution { List<List<Integer>> nums = new ArrayList<>(); List<Integer>
num= new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { dfs(1
, n, k); return nums; } public void dfs(int i, int n, int k) { if(num.size() + n
- i + 1 < k) return;//剪枝 if(num.size() == k) { nums.add(new ArrayList<Integer>(
num)); return; }//重要的事情最先做 num.add(i);//装 dfs(i + 1, n, k); num.remove(num.size(
) - 1);//回溯（不装） dfs(i + 1, n, k); } }

GitHub

Gitee