import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class _77 {
    static class Solution1 {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> res = new ArrayList<>();
            dfs(new ArrayList<>(), res, n, 1, k);
            return res;
        }

        public void dfs(List<Integer> path, List<List<Integer>> res, int n, int cur, int k) {
            if (path.size() == k) {
                res.add(new ArrayList<>(path));
                return;
            }
            if (cur > n) return;
            path.add(cur);
            dfs(path, res, n, cur + 1, k);
            path.remove(path.size() - 1);
            dfs(path, res, n, cur + 1, k);
        }
    }

    static class Solution2 {
        public List<List<Integer>> combine(int n, int k) {
            LinkedList<List<Integer>> q = new LinkedList<>();
            q.offer(new ArrayList<>());
            while (q.peekFirst().size() < k) {
                List<Integer> cur = q.poll();
                int limit = 1;
                if (cur.size() != 0) {
                    limit = cur.get(cur.size() - 1) + 1;
                }
                for (int i = limit; i <= n; i++) {
                    List<Integer> copy = new ArrayList<>(cur);
                    copy.add(i);
                    q.offer(copy);
                }
            }
            return q;
        }
    }

}