【回溯】B008_组合（回溯 | 剪枝）

一、题目描述

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

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

二、题解

(1) 经典回溯

其实，item 还可以声明为一个 $stack$stack。

public List<List<Integer>> combine(int n, int k) {
  LinkedList<List<Integer>> resList = new LinkedList<>();
  backtrack1(1, n, k, new LinkedList<>(), resList);
  return resList;
}

/**
 * @date: 2/4/2020 9:17 PM
 * @Execution info：30ms 击败 48% 的j，MB 击败 13% 的j
 */
private void backtrack1(int begin, int n, int k, LinkedList<Integer> item, List<List<Integer>> resList) {
  if(item.size() == k) {
    resList.add(new LinkedList<>(item));
    return;
  }
  for (int i = begin; i <= n; i++) {
    item.addLast(i);
    backtrack1(i+1, n, k, item, resList);
    item.removeLast();
  }
}

复杂度分析

• 时间复杂度： $O()$O()，

---

(2) 回溯剪枝

$for$for 循环中没必要到 $n$n。比如，$n = 5，k = 4，temp.size( ) == 1$n=5，k=4，temp.size()==1，代表还需要 $（4 - 1 = 3）$（4−1=3） 个数字，如果 $i = 4$i=4 的话，后面顶多把 $4$4 和 $5$5 加到 $item$item 中，加完 $item.size()$item.size() 才等于 $1 + 2 = 3$1+2=3，不够 $4$4 个，所以 $i$i 没必要等于 $4$4。

• $max(i) + 还需寻找的数的个数 - 1 = n$max(i)+还需寻找的数的个数−1=n
• $k - item.size()$k−item.size()：还需寻找的数的个数。

/**
 * @date: 2/4/2020 11:45 PM
 * @Execution info：3ms 击败 87.79% 的j，MB 击败 57% 的j
 */
private void backtrack2(int begin, int n, int k, LinkedList<Integer> item, List<List<Integer>> resList) {
  if(item.size() == k) {
    resList.add(new LinkedList<>(item));
    return;
  }
  for (int i = begin; i <= n-(k-item.size())+1; i++) {
    item.addLast(i);
    backtrack1(i+1, n, k, item, resList);
    item.removeLast();
  }
}