剑指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<List<Integer>> combine1 = combine.combine(4, 2);
        System.out.println(combine1);
    }
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new LinkedList<>();
        LinkedList<Integer> combination = new LinkedList<>();
//        i相当于回溯树的层数
        helper(n,k,1,combination,result);
        return result;
    }

    private void helper(int n, int k,int i ,LinkedList<Integer> combination, List<List<Integer>> 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();
        }
    }
}