leetcode77. 组合

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

题目描述

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

解题思路

这题就是找出固定长度的子集。和leetcode78子集相比，其实是子集的一部分。
nums = [1,2,3] 为例，刚才让你求所有子集，就是把所有节点的值都收集起来；现在你只需要把第 2 层（根节点视为第 0 层）的节点收集起来，就是大小为 2 的所有组合：

所以是子集的一部分，我们还可以用回溯算法的框架去解决。
result = []
def process(选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择

代码演示

class Solution {//答案LinkedList<List<Integer>> ans = new LinkedList<>();//每次递归时做出的选择LinkedList<Integer> track = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {process(1,n,k);return ans;}/*** 回溯算法 递归* start 每次起始位置*/public void process(int start,int n,int k){//base case 越界时 如果长度不对，直接返回不是我们要的答案if(start > n && k != track.size() ){return ;}//长度相等时，是需要的答案，加入到答案里if(k == track.size()){ans.add(new LinkedList<>(track));return;}//回溯算法可以做出选择的列表for(int i = start;i <= n ;i++){//做出选择track.addLast(i);//递归 去下一个位置 继续选择process(i + 1,n,k);//回溯，撤销选择track.removeLast();}}
}

递归专题

leetcode198. 打家劫舍

整数拆分问题

leetcode213. 打家劫舍 II

leetcode198. 打家劫舍

leetcode174. 地下城游戏

打败怪兽的概率

leetcode688. 骑士在棋盘上的概率