77. 组合

悠悠 2024-03-31 15:16 61阅读 0赞

> **保持忙碌。**——《人性的优点》

### 77. 组合 ###

给定两个整数 n 和 k，返回范围 \[1, n\] 中所有可能的 k 个数的组合。

你可以按 **任何顺序** 返回答案。

##### 示例 1： #####

> 输入：n = 4, k = 2  
> 输出：  
> \[  
> \[2,4\],  
> \[3,4\],  
> \[2,3\],  
> \[1,2\],  
> \[1,3\],  
> \[1,4\],  
> \]

##### 示例 2： #####

> 输入：n = 1, k = 1  
> 输出：\[\[1\]\]

##### 提示： #####

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

##### 思路：（回溯） #####

*  如果解决一个问题有多个步骤，每一个步骤有多种方法，题目又要我们找出所有的方法，可以使用回溯算法；
 *  回溯算法是在一棵树上的 深度优先遍历（因为要找所有的解，所以需要遍历）；
 *  组合问题，相对于排列问题而言，不计较一个组合内元素的顺序性（即 \[1, 2, 3\] 与 \[1, 3, 2\] 认为是同一个组合），因此很多时候需要按某种顺序展开搜索，这样才能做到不重不漏。

#### 代码：（Java） ####

import java.util.ArrayList;
    import java.util.List;
    
    public class combine_backtracking {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int n = 4;
    		int k = 2;
    		System.out.println(combine(n,k));
    
    	}
    	public static List<List<Integer>> combine(int n, int k) {
        
    		List<List<Integer>> combinations = new ArrayList<>();
    		if(k <= 0 || n < k) {
        
    			return combinations;
    		}
    		List<Integer> combination = new ArrayList<>();
    		boolean [] hasVisited = new boolean[n+1];
    		backTracking(combinations, combination, hasVisited, 1, n , k);
    		return combinations;
        }
    	private static void backTracking(List<List<Integer>> combinations, List<Integer> combination, boolean[] hasVisited,int begin, int n, int k) {
        
    		// TODO 自动生成的方法存根
    		if(combination.size() == k) {
        
    			combinations.add(new ArrayList<>(combination));
    			return;
    		}
    		for(int i = begin; i <= n; i++) {
        
    			if(hasVisited[i] == true) {
        
    				continue;
    			}
    			combination.add(i);
    			hasVisited[i] = true;
    			backTracking(combinations, combination, hasVisited, i ,n , k);
    			combination.remove(combination.size() - 1);
    			hasVisited[i] = false;
    		}
    	}
    }

##### 运行结果： #####

![在这里插入图片描述][e07e26e238fd47fa94792bf668d2dcda.png]

##### 相同解法的题目： #####

[257. 二叉树的所有路径][257.]  
[79. 单词搜索][79.]  
[93. 复原 IP 地址][93. _ IP]  
[17. 电话号码的字母组合][17.]  
[46. 全排列][46.]  
[47. 全排列 II][47. _ II]

##### 注：仅供学习参考 #####

题目来源：[力扣][Link 1]

[e07e26e238fd47fa94792bf668d2dcda.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/b783c0e52e6a4ae899604177a6aaabac.png
[257.]: https://blog.csdn.net/weixin_43412762/article/details/128148704?spm=1001.2014.3001.5502
[79.]: https://blog.csdn.net/weixin_43412762/article/details/128131522?spm=1001.2014.3001.5502
[93. _ IP]: https://blog.csdn.net/weixin_43412762/article/details/128114845?spm=1001.2014.3001.5502
[17.]: https://blog.csdn.net/weixin_43412762/article/details/128097224?spm=1001.2014.3001.5502
[46.]: https://blog.csdn.net/weixin_43412762/article/details/128160319?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22128160319%22%2C%22source%22%3A%22weixin_43412762%22%7D
[47. _ II]: https://blog.csdn.net/weixin_43412762/article/details/128172523?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22128172523%22%2C%22source%22%3A%22weixin_43412762%22%7D
[Link 1]: https://leetcode.cn/problems/combinations/description/