Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

    Example:

    1. Input: n = 4, k = 2
    2. Output:
    3. [
    4.   [2,4],
    5.   [3,4],
    6.   [2,3],
    7.   [1,2],
    8.   [1,3],
    9.   [1,4],
    10. ]

    题意

    从n个数中选取k个组成集合，输出所有这样的集合。

    思路

    回溯法，注意剪枝。

    代码实现

    1. class Solution {
    2.     public List<List<Integer>> combine(int n, int k) {
    3.         List<List<Integer>> ans = new ArrayList<>();
    4.         combine(n, k, 1, new ArrayList<>(), ans);
    5.         return ans;
    6.     }
    8.     private void combine(int n, int k, int cur, List<Integer> list, List<List<Integer>> ans) {
    9.         if (list.size() == k) {
    10.             ans.add(new ArrayList<>(list));
    11.             return;
    12.         }
    14.         // 只有当剩余元素数加上已加入列表元素数大于等于k时，才需要继续递归
    15.         for (int i = cur; n - i + 1 >= k - list.size(); i++) {
    16.             list.add(i);
    17.             combine(n, k, i + 1, list, ans);
    18.             list.remove(list.size() - 1);
    19.         }
    20.     }
    21. }