力扣77. 组合

Problem: 77. 组合

题目描述

思路及解法

1.定义一个变量 res 用于存储所有的组合结果，这是一个 List<List> 类型的链表。
2.定义一个变量 track 用于存储当前路径，这是一个 LinkedList 类型的链表。
3.定义主函数 combine：

3.1.接受两个参数 n 和 k，分别表示范围和组合的长度。
3.2.调用辅助函数 backtrack 从数字 1 开始进行回溯。

4.定义辅助函数 backtrack：

4.1.参数：start 表示当前选择的起始位置，n 表示范围，k 表示组合的长度。
4.2.基本结束条件：如果当前路径 track 的长度等于 k，将其加入到结果 res 中并返回。
4.3.循环从 start 到 n，尝试每一个可能的选择：

4.3.1.将当前选择加入路径 track 中。
4.3.2.递归调用 backtrack，选择范围从 i + 1 开始，确保组合不重复。
4.3.3.撤销选择，将最后一个加入的元素从 track 中移除。

复杂度

时间复杂度:

$O(C_n^k)$

空间复杂度:

$O(n+C_n^k)$

Code

class Solution {
    // Record the recursive path of the backtracking algorithm
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();

    /**
     * Combinations
     *
     * @param n Given number
     * @param k Given number
     * @return List<List < Integer>>
     */
    public List<List<Integer>> combine(int n, int k) {
        backtrack(1, n, k);
        return res;
    }

    /**
     * Backtracking implementation function
     *
     * @param start Decision stage
     * @param n     Given number
     * @param k     Given number
     */
    private void backtrack(int start, int n, int k) {
        if (track.size() == k) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = start; i < n; ++i) {
            track.addLast(i);
            backtrack(i + 1, n, k);
            track.removeLast();
        }
    }
}