Leetcode77组合

77组合

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

示例:

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combinations 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

多叉树剪枝

class Solution:
    def __init__(self):
        self.result = None
        self.stack = None

    def combine(self, n: int, k: int) -> [[int]]:
        if type(n) is not int or type(k) is not int:
            raise Exception("Invalid input, must be int")
        if n<=0 or k <=0:
            raise Exception("Invalid input, must be positive")
        if n < k:
            raise Exception("n < k")
        self.result = []
        self.stack = []
        for i in range(1, n+1):
            self._recursiveGenarate(i, n, k)
        return self.result

    def _recursiveGenarate(self, start, end, k):
        if (end - start + 1 < k):
            return
        if k == 1:
            self.stack.append(start)
            self.result.append(self.stack.copy())
            self.stack.pop(-1)
        else:
            self.stack.append(start)
            for i in range(start+1, end+1):
                self._recursiveGenarate(i, end, k-1)
            self.stack.pop(-1)

import java.util.*;

class Solution {
    private List<List<Integer>> result;
    private List<Integer> buffer;

    Solution() {
    }

    public List<List<Integer>> combine(int n, int k) {
        // exception conditions
        // n,k is not int
        // n<=0 || k <= 0
        // n<k
        result = new ArrayList<>();
        buffer = new ArrayList<>();
        for (int i = 1; i <= n; i++)
            inorderTraversal(i, n, k);
        return result;
    }

    private void inorderTraversal(int start, int end, int k) {
        if (end + 1 - start < k)
            return;
        if (k == 1) {
            buffer.add(start);
            result.add(new ArrayList<>(buffer));
            buffer.remove(buffer.size() - 1);
        } else {
            buffer.add(start);
            for (int i = start + 1; i <= end; i++)
                inorderTraversal(i, end, k - 1);
            buffer.remove(buffer.size() - 1);
        }
    }
}