import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.Deque;

import java.util.List;

public class Combine_77 {

/**

* 使用dfs算法求解

* @param n

* @param k

* @return

*/

// 1. dfs递归函数为什么要这样定义

// 2. 为什么要用Deque

public List<List<Integer>> combine(int n, int k) {

List<List<Integer>> res = new ArrayList<>();

if (k <= 0 || n < k) {

return res;

}

Deque<Integer> path = new ArrayDeque<>();

dfs(n, k, 1, path, res);

return res;

}

private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {

if (path.size() == k) {

res.add(new ArrayList<>(path));

return;

}

for (int i = begin; i <= n; i++) {

path.addLast(i);

dfs(n, k, i + 1, path, res);

path.removeLast();

}

}

}