🌗 77. 组合

难度: 🌗

问题描述

---

解法 1 - 二叉树思想

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        // 思路： 
        // 前提  1 - n 说明没有重复元素
        LinkedList<Integer> path = new LinkedList<>();
        mySol(n, k, 1, path);
        return res;
    }

    private void mySol(int n, int k, int index, LinkedList<Integer> path) {
        // 递归终止条件
        if(path.size() == k) {
            res.add(new LinkedList<>(path));
            return;
        }
        if(index > n) {
            return;
        }
        // size < k && index <= n
        // 两种情况，取 当前元素加入 path 或者 不要当前元素
        mySol(n, k, index + 1, path);
        path.addLast(index);
        mySol(n, k, index + 1, path);
        path.removeLast();
    }
}

---

输出 1

---

解法 2 - 回溯 + 优化

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        // 思路:
        // 回溯 & 剪枝
        LinkedList<Integer> path = new LinkedList<>();
        mySol(n, k, 1, path);
        return res;
    }

    private void mySol(int n, int k, int cur, LinkedList<Integer> path) {
        // 递归终止条件
        if(path.size() == k) {
            res.add(new LinkedList<>(path));
            return;
        }
        for(int i = cur; i <= n; i ++) {
            // [i, n] 中还需要选取 k - path.size() 个元素
            // i 的最大值为 n - max + 1 == k - size()
            // 否则就剩下一个元素的化，理论上还需要2个元素才能达到 K 个数，这样肯定不成立
            // max = n + 1 - k + path.size()
            if(i > n + 1 - k + path.size()) {
                break; // 剪枝
            }
            path.addLast(i);
            mySol(n, k, i + 1, path);
            path.removeLast();
        }
    }
}

---

输出