来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/combinations
目录
一、题目描述
给定两个整数 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, 2, 3] 与 [1, 3, 2] 认为是同一个组合），因此很多时候需要按某种顺序展开搜索，这样才能做到不重不漏。
三、方法
既然是树形问题上的 深度优先遍历，因此首先画出树形结构。例如输入：n = 4, k = 2，我们可以发现如下递归结构：
- 如果组合里有 1 ，那么需要在 [2, 3, 4] 里再找 1个数；
- 如果组合里有 2 ，那么需要在 [3, 4] 里再找 1个数。注意：这里不能再考虑 1，因为包含 1 的组合，在第 1 种情况中已经包含。
依次类推（后面部分省略），以上描述体现的 递归 结构是：在以 nnn 结尾的候选数组里，选出若干个元素。画出递归结构如下图：
四、代码实现（Java）
package backtracking;
import java.util.ArrayList;
import java.util.List;
public class Combine_77 {
public static void main(String[] args) {
int n = 4;
int k = 2;
List<List<Integer>> lists = combine(n, k);
System.out.println(lists);
}
public static List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
//遍历,从1开始
backtrack(res,path,n,k,1);
return res;
}
private static void backtrack(List<List<Integer>> res,List<Integer> path,int n,int k,int begin){
if (path.size() == k){
res.add(new ArrayList<>(path));
return;
}
//遍历可能的搜索起点
for (int i = begin; i <= n ; i++) {
if (path.contains(i)){
continue;
}
path.add(i);
backtrack(res,path,n,k,i+1);
path.remove(path.size()-1);
}
}
}