77. Combinations

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

public List<List<Integer>> combine(int n, int k) {
    ArrayList<List<Integer>> res = new ArrayList<>();
    if (n <= 0 || k > n) {
        return res;
    }
    helper(1, n, k, new ArrayList<Integer>(), res);
    return res;
}

private void helper(int currentVal, int limit, int count, ArrayList<Integer> path, ArrayList<List<Integer>> res) {
    if (count == 0) {
        res.add(new ArrayList<Integer>(path));
        return;
    }
    if (currentVal > limit) {
        return;
    }
    
    for (int i = currentVal; i <= limit; i++) {
        path.add(i);
        helper(i + 1, limit, count - 1, path, res);
        path.remove(path.size() - 1);
    }
}

时间复杂度为题解个数 n!/ (n - k)! / k!