Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2Output:[  [2,4],  [3,4],  [2,3],  [1,2],  [1,3],  [1,4],]

难度：medium

题目：给定整数n 和k, 返回1到n 中k个数的所有组合。

思路：递归+剪枝

Runtime: 4 ms, faster than 93.58% of Java online submissions for Combinations.

class Solution {    public List
    
     
      > combine(int n, int k) {        List
      
       
        > result = new ArrayList<>();        combine(n, 1, k, new Stack<>(), result);                return result;    }        private void combine(int n, int begin, int k, Stack
        
          stack, List
         
          
           > result) { if (k <= 0) { result.add(new ArrayList<>(stack)); return; } for (int i = begin; i <= n - k + 1; i++) { stack.push(i); combine(n, i + 1, k - 1, stack, result); stack.pop(); } }}