剑指offer80：包含k个元素的组合

剑指offer80：包含k个元素的组合

**题目：**给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
输入: n = 1, k = 1
输出: [[1]]
解析：
该题的思路和剑指offer79题大致相同，这是上一题的思路图：
如果n=3，k=2，找到所有k个数的组合，那在上一题的基础上筛选就可以了，比如画红圈的地方。

代码：

import java.util.linkedList;
import java.util.List;

public class Combine {
    public static void main(String[] args) {
        Combine combine = new Combine();
        List> combine1 = combine.combine(4, 2);
        System.out.println(combine1);
    }
    public List> combine(int n, int k) {
        List> result = new linkedList<>();
        linkedList combination = new linkedList<>();
//        i相当于回溯树的层数
        helper(n,k,1,combination,result);
        return result;
    }

    private void helper(int n, int k,int i ,linkedList combination, List> result) {
//        如果combination的列表中的元素个数到达k个，result则添加combination的拷贝
        if (combination.size() == k){
            result.add(new linkedList<>(combination));
        }else if (i <= n){
            helper(n,k,i+1,combination,result);
            combination.add(i);
            helper(n,k,i+1,combination,result);
//            从列表中删除并返回最后一个元素
            combination.removeLast();
        }
    }
}