Leetcode-77. 组合

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

示例:

输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
解题思路
和子集问题一样，只不过这里有结束条件，也就是我们只要长度为k的子集
还是回溯算法解答

class Solution {
    List<List<Integer>> res=new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        if( k<=0 || n<=0 ) return res;
        LinkedList<Integer> track=new LinkedList<>();
        backtrack(track,n,k,1);
        return res;
    }

    public void backtrack(LinkedList<Integer> track,int n,int k,int start){
        if(track.size()==k){//k个则满足条件
            res.add(new LinkedList(track));
        }
        //和子集的区别是结束条件不同，和排列的区别是一个排除重复元素，一个排除前边的元素
        for(int i=start;i<=n;i++){
            track.add(i);
            backtrack(track,n,k,i+1);
            track.removeLast();
        }
    }
}