解法一：回溯

可以加上剪枝操作，会更快。

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.LinkedList;
  4. import java.util.List;
  5. import java.util.Collections;
  7. class Solution {
  8.     List<List<Integer>> ans;
  9.     Integer[] nums;
  11.     public List<List<Integer>> combine(int n, int k) {
  12.         ans = new LinkedList<>();
  13.         nums = new Integer[k];
  14.         build(n, k, 0, 1);
  15.         return ans;
  16.     }
  18.     private void build(int n, int k, int index, int start) {
  19.         // 剪枝, 保证剩下可选的数必须多于待选的数量
  20.         if (n - start + 1 < k - index) {
  21.             return;
  22.         }
  23.         if (index == k) {
  24.             List<Integer> temp = new ArrayList<>(k);
  25.             Collections.addAll(temp, nums);
  26.             ans.add(temp);
  27.             return;
  28.         }
  29.         for (int i = start; i <= n; ++i) {
  30.             nums[index] = i;
  31.             build(n, k, index + 1, i + 1);
  32.         }
  33.     }
  34. }