组合

题目

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

示例:

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

解题思路

本题为全排列系列的衍生题目，统归回溯系列，不同与全排列需要用额外数组visited记录访问性，该题另有特殊要求。
首先看，全排列的时候结果为以下：
[[1,2],[1,3],[1,4],[2,1],[2,3],[2,4],[3,1],[3,2],[3,4],[4,1],[4,2],[4,3]]
其中，[1,2]和[2,1]；[1,3]和[3,1]...都出现了题目不要求的重复现象，那怎么办----继续剪枝。

比如当1迭代完成，回溯回来迭代2时候，就不能再回到1，否则就出现了[1,2]，[2,1]这种现象。
所以该题有另一种解决方案：通过不断递增的起始点来对结果实现收敛，迭代2时候，起始点就是2，所以只会找出2之后的组合来，也就符合了题目要求。

另外，因为起始点不断在递增，所以也不需要用visited来标记访问性，因为访问过数字的已经被上一步一起剪枝了。

代码

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List list = new ArrayList();
        getSubArray (list,new ArrayList(),n,1,k);
        return list;
    }
    public void getSubArray (List res,List temp, int n,int begin, int len){
        if (len == temp.size()){
            res.add(new ArrayList(temp));
            return;
        }
        for (int i = begin; i <= n; i++){
            temp.add(i);
            getSubArray(res,temp,n,i+1,len);
            temp.remove(temp.size() - 1);
        }
    }
}