描述

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例

示例 1:

  1. 输入: n = 4, k = 2
  2. 输出:
  3. [
  4.   [2,4],
  5.   [3,4],
  6.   [2,3],
  7.   [1,2],
  8.   [1,3],
  9.   [1,4],
  10. ]

示例 2:

输入: n = 1, k = 1
输出: [[1]]

提示

  • 1 <= n <= 20
  • 1 <= k <= n

解题思路

回溯算法 + 剪枝（Java）

这里说一下剪枝，其实很好理解，就是当递归到后面都不可能满足条件时，提前结束这轮递归。
这道题的剪枝操作是由 n - i + 1 >= k - path.size() 推出来的。

代码

class Solution {
    List<Integer> path = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> combine(int n, int k) {
        dfs(1, n, k, path);
        return ans;
    }
    public void dfs(int cur, int n, int k, List<Integer> path) {
        if (path.size() == k) {
            ans.add(new ArrayList<Integer>(path));
            return;
        }
        for (int i = cur; i <= n - (k - path.size()) + 1; i++) { // 剪枝操作
            path.add(i);
            dfs(i + 1, n, k, path);
            path.remove(path.size() - 1);
        }
    }
}