LeetCode - Medium - 77. Combinations

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

## Topic ##

*  Backtracking

## Description ##

[https://leetcode.com/problems/combinations/][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**:

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

**Example 2**:

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

**Constraints**:

*  1 <= `n` <= 20
 *  1 <= `k` <= n

## Analysis ##

### 初次尝试 ###

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

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

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

int n = 100;
    for (int i = 1; i <= n; i++) { 
        for (int j = i + 1; j <= n; j++) { 
            for (int k = j + 1; k <= n; n++) { 
                System.out.println(i + " " + j + " " + k);
            }
        }
    }

如果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][]

最后，函数签名如下：

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

#### 终止条件 ####

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

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

![5e2a0d9c7be6685973c80afb25097fe1.png][]

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

终止条件代码如下：

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

#### 遍历过程 ####

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

![0658df3791dc8ee88bb1cd5933f06e59.png][]

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

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

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

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

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

#### 小结 ####

最终代码如下：

在概论谈论到回溯模板：

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

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

### 剪枝优化 ###

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

遍历的代码如下：

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

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

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

如图所示：

![4dfd1455869261e04d3f7d6304728c9f.png][]

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

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

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

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循环是：

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

优化后整体代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    public class Combinations { 
    
    	// 剪枝优化后的
    	public List<List<Integer>> combine2(int numRange, int expectedSize) { 
    		List<List<Integer>> result = new ArrayList<>();
    		List<Integer> path = new ArrayList<>();
    		backtracking2(path, numRange, expectedSize, 1, result);
    		return result;
    	}
    
    	private void backtracking2(List<Integer> path, int numRange, int expectedSize, int startIndex,
    			List<List<Integer>> result) { 
    		if (path.size() == expectedSize) { 
    			result.add(new ArrayList<>(path));
    			return;
    		}
    
    		for (int i = startIndex; i <= numRange - (expectedSize - path.size()) + 1; i++) { 
    			path.add(i);
    			backtracking(path, numRange, expectedSize, i + 1, result);
    			path.remove(path.size() - 1);
    		}
    	}
    }

### 参考资料 ###

[回溯算法：求组合问题！][Link 1]

[回溯算法：组合问题再剪剪枝][Link 2]

## Submission ##

import java.util.ArrayList;
    import java.util.List;
    
    public class Combinations { 
    	public List<List<Integer>> combine1(int numRange, int expectedSize) { 
    		List<List<Integer>> result = new ArrayList<>();
    		List<Integer> path = new ArrayList<>();
    		backtracking(path, numRange, expectedSize, 1, result);
    		return result;
    	}
    
    	private void backtracking(List<Integer> path, int numRange, int expectedSize, int startIndex,
    			List<List<Integer>> result) { 
    		if (path.size() == expectedSize) { 
    			result.add(new ArrayList<>(path));
    			return;
    		}
    
    		for (int i = startIndex; i <= numRange; i++) { 
    			path.add(i);
    			backtracking(path, numRange, expectedSize, i + 1, result);
    			path.remove(path.size() - 1);
    		}
    	}
    
    	// 剪枝优化后的
    	public List<List<Integer>> combine2(int numRange, int expectedSize) { 
    		List<List<Integer>> result = new ArrayList<>();
    		List<Integer> path = new ArrayList<>();
    		backtracking2(path, numRange, expectedSize, 1, result);
    		return result;
    	}
    
    	private void backtracking2(List<Integer> path, int numRange, int expectedSize, int startIndex,
    			List<List<Integer>> result) { 
    		if (path.size() == expectedSize) { 
    			result.add(new ArrayList<>(path));
    			return;
    		}
    
    		for (int i = startIndex; i <= numRange - (expectedSize - path.size()) + 1; i++) { 
    			path.add(i);
    			backtracking(path, numRange, expectedSize, i + 1, result);
    			path.remove(path.size() - 1);
    		}
    	}
    }

## Test ##

import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder;
    import static org.junit.Assert.*;
    
    import java.util.Arrays;
    
    import org.junit.Test;
    
    public class CombinationsTest { 
    
    	@Test
    	@SuppressWarnings("unchecked")
    	public void test1() { 
    		Combinations obj = new Combinations();
    
    		Object[] expected = { Arrays.asList(2,4),
    				Arrays.asList(3,4),
    				Arrays.asList(2,3),
    				Arrays.asList(1,2),
    				Arrays.asList(1,3),
    				Arrays.asList(1,4)};
    		
    		assertThat(obj.combine1(4, 2), containsInAnyOrder(expected));
    		assertThat(obj.combine1(1, 1), containsInAnyOrder(Arrays.asList(1)));
    		assertThat(obj.combine1(4, 4), containsInAnyOrder(Arrays.asList(1, 2, 3, 4)));
    		assertThat(obj.combine1(4, 3), containsInAnyOrder(Arrays.asList(1, 2, 3), Arrays.asList(1, 3, 4),//
    				Arrays.asList(1, 2, 4), Arrays.asList(2, 3, 4)));
    	}
    	
    	@Test
    	@SuppressWarnings("unchecked")
    	public void test2() { 
    		Combinations obj = new Combinations();
    		
    		Object[] expected = { Arrays.asList(2,4),
    				Arrays.asList(3,4),
    				Arrays.asList(2,3),
    				Arrays.asList(1,2),
    				Arrays.asList(1,3),
    				Arrays.asList(1, 4) };
    
    		assertThat(obj.combine2(4, 2), containsInAnyOrder(expected));
    		assertThat(obj.combine2(1, 1), containsInAnyOrder(Arrays.asList(1)));
    		assertThat(obj.combine2(4, 4), containsInAnyOrder(Arrays.asList(1, 2, 3, 4)));
    		assertThat(obj.combine2(4, 3), containsInAnyOrder(Arrays.asList(1, 2, 3), Arrays.asList(1, 3, 4), //
    				Arrays.asList(1, 2, 4), Arrays.asList(2, 3, 4)));
    	}
    }

[https_leetcode.com_problems_combinations]: https://leetcode.com/problems/combinations/
[2df72ab5309911f33ff57494820029ca.png]: /images/20221119/051ae82a7cbe44678edca5f465c7eacf.png
[17659efcd21bdc15a428142a0d16e46d.png]: /images/20221119/0221da127f02433fb838343bd1ab0a79.png
[5e2a0d9c7be6685973c80afb25097fe1.png]: /images/20221119/375a2bbfefd0474996ff74934668db07.png
[0658df3791dc8ee88bb1cd5933f06e59.png]: https://img-blog.csdnimg.cn/img_convert/0658df3791dc8ee88bb1cd5933f06e59.png
[4dfd1455869261e04d3f7d6304728c9f.png]: https://img-blog.csdnimg.cn/img_convert/4dfd1455869261e04d3f7d6304728c9f.png
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247485253&idx=1&sn=8332edaabc9bf43e45835bce7964ce88&scene=21#wechat_redirect
[Link 2]: https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247485264&idx=1&sn=860006efeb344db329b555a8b2711769&scene=21#wechat_redirect