组合

List<List<Integer>> ans = new ArrayList<>();
LinkedList<Integer> item = new LinkedList<>();

public List<List<Integer>> combine(int n, int k) {
    dfsCombine(n, k, 1);
    return ans;
}

public void dfsCombine(int n, int k, int index) {
    if (item.size() == k) {
        // 如果长度达到k，保存结果。
        ans.add(new ArrayList<>(item));
        return;
    }

    if (item.size() + n - index + 1 < k) {
        // 如果剩下的数字不够组合成k个数，则不满足要求。
        return;
    }
    // 选择当前元素，然后进行递归。 
    item.add(index);
    dfsCombine(n, k, index + 1);
    
    // 不选择当前元素，然后进行递归，也是一种回溯。
    item.removeLast();
    dfsCombine(n, k, index + 1);
}