力扣77——组合

这道题主要利用栈就可以解决，优化时需要考虑那些失败情况。

原题

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

原题url：https://leetcode-cn.com/problems/combinations/

解题

递归获取

一开始的想法就是遍历递归获取，利用一个 stack 存储中间结果，不断进行出栈入栈，这样肯定就能拿全。

让我们来看看代码：

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        if (k == 0) {
            return new LinkedList<>();
        }
        if (n == 0) {
            return new LinkedList<>();
        }
        
        List<List<Integer>> result = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();
        dfs(n, k, 1, stack, result);

        return result;
    }

    public void dfs(int n, int remain, int index, Stack<Integer> stack, List<List<Integer>> result) {
        for (int i = index; i <= n; i++) {
                        // 加入stack中
            stack.push(i);
                        // 是否加到k个数
            if (remain - 1 == 0) {
                result.add(new LinkedList<>(stack));
            } else {
                dfs(n, remain - 1, i + 1, stack, result);
            }
                        // 将数从stack中拿出
            stack.pop();
        }       
    }
}

提交OK，执行用时：73 ms，内存消耗：44 MB。是否还可以优化呢？

剪枝

今天看到了一个词剪枝，其实这个词是回溯剪枝，回溯大家都懂，剪枝其实就是一种优化，减少回溯中不需要的情况。

从上面的代码可以看出，在回溯中的遍历，并不需要一直遍历到 n。比如：从 7 个数中取 4 个数，开始的时候遍历到 4 就足够了，因为从 5 开始凑不齐 4 个数，之后的遍历也是同样如此。

明知失败的事不需要一直进行到最后，和快速失败有些类似，接下来看看优化后的代码：

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        if (k == 0) {
            return new LinkedList<>();
        }
        if (n == 0) {
            return new LinkedList<>();
        }
        
        List<List<Integer>> result = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();
        dfs(n, k, 1, stack, result);

        return result;
    }

    public void dfs(int n, int remain, int index, Stack<Integer> stack, List<List<Integer>> result) {
            // 当剩余没有遍历的数，比还需要遍遍历的数少时，也可以不用继续了。
        for (int i = index; i <= n && (n - i + 1 >= remain); i++) {
                        // 加入stack中
            stack.push(i);
                        // 是否加到k个数
            if (remain - 1 == 0) {
                result.add(new LinkedList<>(stack));
            } else {
                dfs(n, remain - 1, i + 1, stack, result);
            }
            stack.pop();
        }       
    }
}