LeetCode - Medium - 77. Combinations

浅浅的花香味﹌ 2023-01-04 14:53 272阅读 0赞

Topic

  • Backtracking

Description

https://leetcode.com/problems/combinations/

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

You may return the answer in any order.

Example 1:

  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. ]

Example 2:

  1. Input: n = 1, k = 1
  2. Output: [[1]]

Constraints:

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

Analysis

初次尝试

直接的想法解法是使用for循环。示例一中n为4，k为2，很容易想到用两个for循环，这样就可以输出和示例中一样的结果，代码如下：

  1. int n = 4;
  2. for (int i = 1; i <= n; i++) { 
  3.     for (int j = i + 1; j <= n; j++) { 
  4.         System.out.println(i + " " + j);
  5.     }
  6. }

输入：n = 100, k = 3 那么就三层for循环，代码如下：

  1. int n = 100;
  2. for (int i = 1; i <= n; i++) { 
  3.     for (int j = i + 1; j <= n; j++) { 
  4.         for (int k = j + 1; k <= n; n++) { 
  5.             System.out.println(i + " " + j + " " + k);
  6.         }
  7.     }
  8. }

如果n为100，k为50呢，那就编写50层for循环，显然这是不可取的。

主角登场

回溯搜索法来了，虽然回溯法也是暴力，但至少能写出来，不像for循环嵌套k层让人绝望。

要解决 n为100，k为50的情况，暴力写法需要嵌套50层for循环，那么回溯法就用递归来解决嵌套层数的问题。

递归来做层叠嵌套（可以理解是开k层for循环），每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了。

回到上面的例子，k为50的情况下，就是递归50层。

在概论谈论到，回溯法解决的问题都可以抽象为树形结构，用树形结构可方便我们理解回溯：

2df72ab5309911f33ff57494820029ca.png

可以看出这个棵树，一开始集合是 1，2，3，4， 从左向右取数，取过的数，不在重复取。

第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2] [1,3] [1,4]，以此类推。

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。

图中可以发现n相当于树的宽度，k相当于树的深度。

那么如何在这个树上遍历，然后收集到我们要的结果集呢？

图中每次搜索到了叶子节点，我们就找到了一个结果。相当于只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。

回溯三弄

函数签名

参数变量如下：

  • List<Integer> path：用来存放符合条件单一结果。
  • List<List<Integer>> result：用来存放符合条件结果的集合。
  • int numRange：对应题目中的n。
  • int expectedSize：对应题目中的k。
  • int startIndex：用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,…,n] ）。

为什么要有这个startIndex呢？

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex。

从下图中红线部分可以看出，在集合[1,2,3,4]取1之后，下一层递归，就要在[2,3,4]中取数了，那么下一层递归如何知道从[2,3,4]中取数呢，靠的就是startIndex。

17659efcd21bdc15a428142a0d16e46d.png

最后，函数签名如下：

  1. private void backtracking(List<Integer> path, int numRange, int expectedSize, 
  2.                           int startIndex, List<List<Integer>> result){ }

终止条件

什么时候到达所谓的叶子节点了呢？

path这个列表大小如果达到expectedSize，说明我们找到了一个子集大小为expectedSize的组合了，在图中path存的就是根节点到叶子节点的路径。如下图红色部分：

5e2a0d9c7be6685973c80afb25097fe1.png

此时用result把path保存起来，并终止本层递归。

终止条件代码如下：

  1. if (path.size() == expectedSize) { 
  2.     result.add(new ArrayList<>(path));
  3.     return;
  4. }

遍历过程

回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。

0658df3791dc8ee88bb1cd5933f06e59.png

如此我们才遍历完图中的这棵树。

for循环每次从startIndex开始遍历，然后用path保存取到的节点i。代码如下：

  1. for (int i = startIndex; i <= numRange; i++) { 
  2.     path.add(i);
  3.     backtracking(path, numRange, expectedSize, i + 1, result);
  4.     path.remove(path.size() - 1);
  5. }

可以看出backtracking（递归函数）通过不断调用自己一直往深处遍历，总会遇到叶子节点，遇到了叶子节点就要返回。

backtracking的下面部分就是回溯的操作了，撤销本次处理的结果，为了下一回循环。

小结

最终代码如下：

  1. import java.util.ArrayList;
  2. import java.util.List;
  4. public class Combinations { 
  5.     public List<List<Integer>> combine1(int numRange, int expectedSize) { 
  6.         List<List<Integer>> result = new ArrayList<>();
  7.         List<Integer> path = new ArrayList<>();
  8.         backtracking(path, numRange, expectedSize, 1, result);
  9.         return result;
  10.     }
  12.     private void backtracking(List<Integer> path, int numRange, int expectedSize, int startIndex,
  13.             List<List<Integer>> result) { 
  14.         if (path.size() == expectedSize) { 
  15.             result.add(new ArrayList<>(path));
  16.             return;
  17.         }
  19.         for (int i = startIndex; i <= numRange; i++) { 
  20.             path.add(i);
  21.             backtracking(path, numRange, expectedSize, i + 1, result);
  22.             path.remove(path.size() - 1);
  23.         }
  24.     }
  25. }

在概论谈论到回溯模板：

  1. void backtracking(参数) {
  2.     if (终止条件) {
  3.         存放结果;
  4.         return;
  5.     }
  7.     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
  8.         处理节点;
  9.         backtracking(路径，选择列表); // 递归
  10.         回溯，撤销处理结果
  11.     }
  12. }

对比一下本题的代码，神同形似。有了这个模板，就有解题的大体方向，不至于六神无主。

剪枝优化

回溯法虽然是暴力搜索，但有时可以剪枝优化一下。

遍历的代码如下：

  1. for (int i = startIndex; i <= numRange; i++) { 
  2.     path.add(i);
  3.     backtracking(path, numRange, expectedSize, i + 1, result);
  4.     path.remove(path.size() - 1);
  5. }

这个遍历的范围是可以剪枝优化的，怎么优化呢？

举一个例子，当n = 4，k = 4，那么第一层for循环的时候，从元素2开始的遍历都没有意义了（最多3个，永远凑不够4个）。在第二层for循环，从元素3开始的遍历都没有意义了（最多2个，永远凑不够3个）,以此类推。

如图所示：

4dfd1455869261e04d3f7d6304728c9f.png

图中每一个节点（图中为矩形），就代表本层的一个for循环，那么每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。

所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

注意代码中i，就是for循环里选择的起始位置。

  1. for (int i = startIndex; i <= n; i++) {

优化过程如下：

  1. 已经选择的元素个数：path.size();
  2. 还需要的元素个数为：k - path.size();

  3. 在集合n中至多要从该起始位置：n - (k - path.size()) + 1，开始遍历。为什么有个+1呢？因为包括起始位置，我们要是一个左闭的集合。

    s = n − ( k − p a t h . s i z e ( ) ) + 1 = n − k + 1 + p a t h . s i z e ( ) s = n - (k - path.size()) + 1 = n - k + 1 + path.size() s=n−(k−path.size())+1=n−k+1+path.size()，式子中的n，k在传参到回溯函数后是固定大小的，那么随着path.size()增大，s减小。

我们举实例说明下，为什么有个+1呢？

举个例子，n = 4，k = 3， 目前已经选取的元素个数为0（path.size为0），n - (k - 0) + 1 = 4 - ( 3 - 0) + 1 = 2。从1或2开始搜索是合理的，可以是组合[1, 2, 3]，[2, 3, 4]。

再举个例子，n = 4，k = 4， 目前已经选取的元素个数为0（path.size为0），n - (k - 0) + 1 = 4 - ( 4 - 0) + 1 = 1。从1开始搜索是合理的，可以是组合[1, 2, 3, 4]。

优化之后的for循环是：

  1. for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

优化后整体代码如下：

  1. import java.util.ArrayList;
  2. import java.util.List;
  4. public class Combinations { 
  6.     // 剪枝优化后的
  7.     public List<List<Integer>> combine2(int numRange, int expectedSize) { 
  8.         List<List<Integer>> result = new ArrayList<>();
  9.         List<Integer> path = new ArrayList<>();
  10.         backtracking2(path, numRange, expectedSize, 1, result);
  11.         return result;
  12.     }
  14.     private void backtracking2(List<Integer> path, int numRange, int expectedSize, int startIndex,
  15.             List<List<Integer>> result) { 
  16.         if (path.size() == expectedSize) { 
  17.             result.add(new ArrayList<>(path));
  18.             return;
  19.         }
  21.         for (int i = startIndex; i <= numRange - (expectedSize - path.size()) + 1; i++) { 
  22.             path.add(i);
  23.             backtracking(path, numRange, expectedSize, i + 1, result);
  24.             path.remove(path.size() - 1);
  25.         }
  26.     }
  27. }

参考资料

回溯算法：求组合问题！

回溯算法：组合问题再剪剪枝

Submission

  1. import java.util.ArrayList;
  2. import java.util.List;
  4. public class Combinations { 
  5.     public List<List<Integer>> combine1(int numRange, int expectedSize) { 
  6.         List<List<Integer>> result = new ArrayList<>();
  7.         List<Integer> path = new ArrayList<>();
  8.         backtracking(path, numRange, expectedSize, 1, result);
  9.         return result;
  10.     }
  12.     private void backtracking(List<Integer> path, int numRange, int expectedSize, int startIndex,
  13.             List<List<Integer>> result) { 
  14.         if (path.size() == expectedSize) { 
  15.             result.add(new ArrayList<>(path));
  16.             return;
  17.         }
  19.         for (int i = startIndex; i <= numRange; i++) { 
  20.             path.add(i);
  21.             backtracking(path, numRange, expectedSize, i + 1, result);
  22.             path.remove(path.size() - 1);
  23.         }
  24.     }
  26.     // 剪枝优化后的
  27.     public List<List<Integer>> combine2(int numRange, int expectedSize) { 
  28.         List<List<Integer>> result = new ArrayList<>();
  29.         List<Integer> path = new ArrayList<>();
  30.         backtracking2(path, numRange, expectedSize, 1, result);
  31.         return result;
  32.     }
  34.     private void backtracking2(List<Integer> path, int numRange, int expectedSize, int startIndex,
  35.             List<List<Integer>> result) { 
  36.         if (path.size() == expectedSize) { 
  37.             result.add(new ArrayList<>(path));
  38.             return;
  39.         }
  41.         for (int i = startIndex; i <= numRange - (expectedSize - path.size()) + 1; i++) { 
  42.             path.add(i);
  43.             backtracking(path, numRange, expectedSize, i + 1, result);
  44.             path.remove(path.size() - 1);
  45.         }
  46.     }
  47. }

Test

  1. import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder;
  2. import static org.junit.Assert.*;
  4. import java.util.Arrays;
  6. import org.junit.Test;
  8. public class CombinationsTest { 
  10.     @Test
  11.     @SuppressWarnings("unchecked")
  12.     public void test1() { 
  13.         Combinations obj = new Combinations();
  15.         Object[] expected = { Arrays.asList(2,4),
  16.                 Arrays.asList(3,4),
  17.                 Arrays.asList(2,3),
  18.                 Arrays.asList(1,2),
  19.                 Arrays.asList(1,3),
  20.                 Arrays.asList(1,4)};
  22.         assertThat(obj.combine1(4, 2), containsInAnyOrder(expected));
  23.         assertThat(obj.combine1(1, 1), containsInAnyOrder(Arrays.asList(1)));
  24.         assertThat(obj.combine1(4, 4), containsInAnyOrder(Arrays.asList(1, 2, 3, 4)));
  25.         assertThat(obj.combine1(4, 3), containsInAnyOrder(Arrays.asList(1, 2, 3), Arrays.asList(1, 3, 4),//
  26.                 Arrays.asList(1, 2, 4), Arrays.asList(2, 3, 4)));
  27.     }
  29.     @Test
  30.     @SuppressWarnings("unchecked")
  31.     public void test2() { 
  32.         Combinations obj = new Combinations();
  34.         Object[] expected = { Arrays.asList(2,4),
  35.                 Arrays.asList(3,4),
  36.                 Arrays.asList(2,3),
  37.                 Arrays.asList(1,2),
  38.                 Arrays.asList(1,3),
  39.                 Arrays.asList(1, 4) };
  41.         assertThat(obj.combine2(4, 2), containsInAnyOrder(expected));
  42.         assertThat(obj.combine2(1, 1), containsInAnyOrder(Arrays.asList(1)));
  43.         assertThat(obj.combine2(4, 4), containsInAnyOrder(Arrays.asList(1, 2, 3, 4)));
  44.         assertThat(obj.combine2(4, 3), containsInAnyOrder(Arrays.asList(1, 2, 3), Arrays.asList(1, 3, 4), //
  45.                 Arrays.asList(1, 2, 4), Arrays.asList(2, 3, 4)));
  46.     }
  47. }

发表评论

表情：
评论列表 （有 0 条评论，272人围观）

还没有评论，来说两句吧...

相关阅读