77. 组合

// LeetCode指定调用方法 
public List<List<Integer>> combine(int n, int k) {

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

    backtracking(1, n, k, result, new ArrayList<>());

    return result;
}

// 回溯，t记录当前可选元素的开始位置，combineList记录当前的组合数
private void backtracking(int t, int n, int k, List<List<Integer>> result, List<Integer> combineList) {

    if (k == 0) {
        result.add(new ArrayList<>(combineList));
        return ;
    }

    // 剪枝（当从n个数中选k个数时，第一个数必定只能在1 ~ (n - k + 1)之间选，以保证后面还有k - 1个数可选）
    for (int i = t; i <= n - k + 1; i++) {
        combineList.add(i);
        backtracking(i + 1, n, k - 1, result, combineList);
        combineList.remove(combineList.size() - 1);
    }
}