LeetCode/77. 组合

77. 组合

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

示例 ：

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

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题一看到排列组合，就还是回溯的问题，至于怎么回溯，其实做了这么多题了，我们应该总结出一套框架了：在回溯中，首先会判断结束条件，如果满足结束条件，就将结果保存并返回；如果不满足结束条件，我们需要递归地将当前数值加入临时数组中，然后再次backtrack，只有当临时数组的长度符合要求时才会递归地返回，此时我们就会得到一个结果值；最后递归返回后将当前值去除，添加别的值进行不同的排列组合，重复以上过程，就会得到全部结果。这道题和全排列问题非常的相似，不同的是这里不是返回所有的排列值，而是返回指定长度的组合结果。这里我们可以将结束条件设置为临时数组长度等于k时就结束，然后在backtrack过程中加入一个start变量以防止数字重复。

具体代码如下：

class Solution {
  	//用于存放结果的链表
    List<List<Integer>> result = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
      	//用于临时存放满足条件的数组
        LinkedList<Integer> track = new LinkedList<>();
        if (k <= 0 || n < k) {
            return result;
        }
        backtrack(n, k, 1, track, result);
        return result;
    }

    void backtrack(int n, int k, int begin, LinkedList<Integer> track, List<List<Integer>> result) {
        //触发结束条件，即如果当前临时数组的长度满足要求直接存储并返回
        if (track.size() == k) {
            result.add(new LinkedList<>(track));
            return;
        }

        for (int i = start; i <= n; i++) {
            //将track中未出现的元素加入
            track.add(i);
            backtrack(n, k, i + 1, track, result);
            //剔除最后一个元素，尝试下一个不同的元素
            track.removeLast();
        }
    }
}