LeetCode_回溯_中等_77.组合

深藏阁楼爱情的钟 2023-10-06 19:05 18阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定两个整数 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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/combinations

## 2.思路 ##

（1）回溯算法

*  为了方便求解题目，可以先用链表 track 来保存每种结果，然后再将其保存到 res 中。
 *  本题使用回溯法的基本思想是：使用递归函数 backTrack(1, n, k) 实现对整个解空间的回溯搜索，backTrack(i, n, k) 搜索解空间的第 i 层子树（即可看作将在 \[1, n\] 中选择的下一个整数）：
    
     *  当 track.size() == k 时，算法搜索至叶结点，即得到了一个 k 个数的组合，并且将其保存到 res 中；
     *  当 track.size() < k 时，此时需要先将当前节点 i（即整数 i）加入到 track 中，然后再从 i + 1 开始进行下一层搜索（即寻找下一个整数，直到找到 k 个整数为止，即 track.size() == k）。除此之外，为了提高搜索的效率，还可以根据“k 个数的组合”这一条件来进行**剪枝优化**，即判断剩余可供选择的整数个数是否够用；
 *  当回溯结束后，返回 res 即可。

相关题目：  
[LeetCode\_回溯\_中等\_78.子集][LeetCode_78.]  
[LeetCode\_回溯\_中等\_90.子集II][LeetCode_90._II]

## 3.代码实现（Java） ##

//思路1————回溯算法
    class Solution {
        
        // res 用于保存最终结果
        List<List<Integer>> res = new ArrayList<>();
    
        // track 用于记录回溯的路径
        List<Integer> track = new ArrayList<>();
    
        public List<List<Integer>> combine(int n, int k) {
        
            backtrack(n, k, 1);
            return res;
        }
    
        public void backtrack(int n, int k, int start) {
        
            if (k == track.size()) {
        
                //找到一个组合，将其保存到 res 中
                res.add(new LinkedList<>(track));
                return;
            }
            /*
    			回溯算法框架
    			i <= n - (k - track.size()) + 1: 此处进行了剪枝操作，即保证剩余可供选择的整数个数够用
    		*/
            for (int i = start; i <= n - (k - track.size()) + 1; i++) {
        
                //做选择
                track.add(i);
                //搜索回溯树的下一层
                backtrack(n, k, i + 1);
                //撤销选择
                track.remove(track.size() - 1);
            }
        }
    }

[LeetCode_78.]: https://blog.csdn.net/weixin_43004044/article/details/119963339
[LeetCode_90._II]: https://blog.csdn.net/weixin_43004044/article/details/120073991